Title: Solving the single machine scheduling problem with general job-dependent past-sequence-dependent setup times and learning effects

Authors: H.M. Soroush

Addresses: Department Statistics and Operations Research, College of Science, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait

Abstract: This paper deals with a single machine scheduling problem with general past-sequence-dependent (psd) setup time and log-linear learning in which the setup times and learning effects are job-dependent. The setup times are unique functions of the length of already processed jobs, and the learning effects show that processing times are unique decreasing functions of job positions. The goal is to find the optimal sequences that minimise objective functions such as 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. Special cases of the resulting problems are solvable in polynomial time; however, the general problems are difficult to solve. We propose branch-and-bound (B&B) methods to derive the optimal sequences for such problems. Computational results show that the proposed methods can solve relatively large problem instances in reasonable amounts of time. [Received 21 December 2010; Revised 25 February 2011; Accepted 8 April 2011]

Keywords: single machine scheduling; learning effect; job dependent setup times; branch and bound; sequence-dependent setup times; optimal sequences.

DOI: 10.1504/EJIE.2012.048857

European Journal of Industrial Engineering, 2012 Vol.6 No.5, pp.596 - 628

Published online: 10 Sep 2014 *

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