Scheduling in a Management Context: Uncertain Processing Times and Non‐Regular Performance Measures*
研究了加工时间不确定且同时惩罚提前和延误的调度问题，提出优先级诱导构建启发式算法，在现实规模问题上平均成本偏差低于1%。
ABSTRACT Decision makers often face scheduling problems in which processing times are not known with certainty. Non‐regular performance measures, in which both earliness and tardiness are penalized, are also becoming more common in both manufacturing and service operations. We model a managerial environment with task processing times (which include sequenceindependent set‐up times) prescribed by three‐parameter lognormal distributions. Upon completion, each task derives a reward given by a particular piecewise‐linear reward function. The objective is to select a sequence of tasks maximizing the expected total reward. The relative generality of the problem renders many enumerative methods inapplicable or computationally intractable. To overcome such difficulties we develop efficient priorityinduced construction (PIC) heuristics which build up a complete schedule by inserting tasks (singly from a list) into a partial sequence of tasks. In each partial and complete sequence a period of idle time is permitted prior to the first task. Performance on realistic‐sized problems is very encouraging, with cost penalties averaging less than one percent.