Title: ACO-based method for single machine scheduling with sequence-dependent setup time and limited capacity warehouse
Author: Shijin Wang
Address: 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.
Int. J. of Industrial and Systems Engineering, 2014 Vol.16, No.3, pp.334 - 364
Available online: 28 Mar 2014