Scheduling in a Management Context: Uncertain Processing Times and Non-Regular Performance Measures*

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.