Authors: H.M. Soroush
Addresses: Department of Statistics and Operations Research, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait
Abstract: This paper deals with a single machine scheduling problem where job attributes are random variables, setup times are sequence-dependent, and a scheduler utilises a cost function to evaluate two criteria associated with a sequence. The objective is to determine the optimal sequence that minimises the scheduler|s expected cost. We show that problem scenarios wherein cost functions are linear, exponential, and fractional can be formulated as Quadratic Assignment Problems (QAPs). Also, special cases with sequence-independent setup times are shown to be solvable optimally in polynomial time. Our computational results on scenarios with sequence-dependent setup times demonstrate that good solutions can be approximated within reasonable amounts of time.
Keywords: single machine scheduling; stochastic bicriteria single machine systems; setup times; QAP; quadratic assignment problem.
International Journal of Planning and Scheduling, 2011 Vol.1 No.1/2, pp.109 - 145
Received: 08 May 2021
Accepted: 12 May 2021
Published online: 24 Dec 2011 *