Scheduling in stochastic bicriteria single machine systems with job-dependent learning effects

A stochastic bicriteria single machine scheduling problem with job-dependent learning effects in which the normal processing times of jobs (i.e., processing times without any learning effects) are random variables was studied. The job-dependent learning effects show that the random actual processing times are unique functions of the positions of jobs in a sequence. The goal was to derive the optimal sequence that minimizes the expected value of a general quadratic function of each pair of criteria consisting of the makespan, total completion time, total lateness, total waiting cost, total waiting time, total absolute differences in completion times, and the sum of earliness, tardiness and common due date penalty. The resultant problems were formulated as quadratic assignment problems that could be solved exactly or heuristically, and proved that their special cases with linear cost functions are solvable in polynomial time. Computational results on problems with quadratic assignment formulations indicated that near-optimal solutions can be obtained with attractive CPU times.