Title: Scheduling in stochastic bicriteria single machine systems with set-up times

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.

DOI: 10.1504/IJPS.2011.044605

International Journal of Planning and Scheduling, 2011 Vol.1 No.1/2, pp.109 - 145

Published online: 31 Dec 2011 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article