Title: ACO-based method for single machine scheduling with sequence-dependent setup time and limited capacity warehouse

Authors: Shijin Wang

Addresses: Department of Management Science and Engineering, School of Economics and Management, Tongji University, Shanghai, 200092, China

Abstract: Much of the research on operations scheduling problems has ignored setup times and also assumes that output warehouse (or buffer) is infinite. While in many real-world production scheduling systems, it requires explicit consideration of sequence-dependent setup times and limited capacity output warehouse. This paper studies a single machine scheduling (SMS) problem considering sequence-dependent setup times and limited capacity output warehouse simultaneously, with the objective of minimising the total tardiness. A mathematical model is constructed to depict the problem. As the problem is NP-hard, a modified ant colony optimisation (ACO) method based on ant system meta-heuristic is presented to solve the problem. Incorporated with different state transition rules due to different combinations of heuristic information, several versions of the ACO method are generated. For each method, parameters are tuned with design of experiments (DOE). Then, based on different settings of experimental simulation, the performance of the methods is discussed and also compared with those of genetic algorithm (GA) and dispatching rules. The results show the feasibility and effectiveness of the proposed method for the considered problem.

Keywords: single machine scheduling; ant colony optimisation; ACO; ant system; sequence-dependent setup times; SDSTs; limited capacity; warehouse capacity; mathematical modelling; design of experiments; DOE; simulation; genetic algorithms; dispatching rules.

DOI: 10.1504/IJISE.2014.060133

International Journal of Industrial and Systems Engineering, 2014 Vol.16 No.3, pp.334 - 364

Published online: 07 Jun 2014 *

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