Scheduling two parallel machines with sequence-dependent setups and a single server

Abstract

This paper presents a scheduling problem on parallel machines with sequence-dependent setup times and setup operations that performed by a single server. The main purpose is to get minimum makespan of the schedule. The system is formulated as genetic algorithm with problem sizes consisting of two machines and 10, 20 and 30 jobs. A genetic algorithm is developed using random data sets . The optimum results are obtained using a string based permutation algorithm which scans all alternatives. As a result, proposed algorithm is e ective to solve P2,SjSTsdjCmax scheduling problem on reasonable runtime and the results of the algorithm which are close to optimum solution values. E ectiveness of the solution is presented considering approximation rates of the genetic algorithm solutions to the optimum results obtained for P2,SjSTsdjCmax problem.

Keywords

• Parallel Machine Scheduling, Genetic Algorithm, Permutation Algorithm

References

1. Abdekhodaee, A.H., Wirth, A., Gan, H.S., “Scheduling two parallel machines with a single server: the general case”, Computers & Operations Research 33: 994-1009 (2006).
2. Abdekhodaee, A.H., Wirth, A., “Scheduling parallel machines with a single server: Some solvable cases and heuristics”, Computers & Operations Research, 29: 295315 (2002).
3. Allahverdi, A., Gupta, J.N., Aldowaisan, T., “A review of scheduling research involving setup considerations”, OMEGA The International Journal of Management Sciences, 27: 219-239 (1999).
4. Allahverdi, A., Mg, C.T., Cheng, T.C., Kovalyov, M.Y., “A survey of scheduling problems with setup times or costs”, European Journal of Operational Research, 187: 985-1032 (2006).
5. Cakar, T., Koker, R., Demir, H.I., “Parallel robot scheduling to minimize mean tardiness with precedence constraints using a genetic algorithm”, Advances in Engineering Software, 39: 4754 (2008).
6. Cheng, T.C.E., Gupta, J.N.D., Wang, G., “A review of flowshop scheduling research with setup times”, Production and Operations Management, 9: 262- 282 (2010).
7. Guinet, A., “Scheduling sequence dependent jobs on identical parallel machines to minimize completion time criteria”, Int. J. Prod. Res., 31 (7): 1579-1594 (1993).
8. Huang, S., Chai, L., Zhang, X., “Parallel dedicated machine scheduling problem with sequence- dependent setups and a single server”, Computers & Industrial Engineering, 58: 165-174 (2009).

9. Kellegoz, T., Toklu, B., Wilson, J., “Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem”, Applied Mathematics and Computation, 199: 590-598 (2008).
10. Kellegoz, T., Toklu, B., Wilson, J., “Elite guided steady-state genetic algorithm for minimizing total tardiness in flowshops”, Computers & Industrial Engineering, 58: 300-306 (2010).
11. Kurz, M.E., Askin, R.G., “Heuristic scheduling of parallel machines with sequence- dependent set-up times”, Int. J. Prod. Res., 39(16): 3747-3769 (2001).
12. Sel, C., “Scheduling parallel machines using genetic algorithms with sequence dependent setup times and a single server”, Master thesis, Kirikkale University, (2010).
13. Sivrikaya, F., Ulusoy, G., “Parallel machine
14. scheduling with earliness and tardiness penalties”, Computers & Operations Research, 26:773-787 (1999).
15. Wilson, A.D., King, R.E., Hodgson, T.J., “Scheduling non-similar groups on a flow line: multiple group setups”, Robotics and Computer- Integrated Manufacturing, 20: 505-515 (2004).
16. Yang, W., Liao, C., “Survey of scheduling research involving setup times”, International Journal of Systems Science, 30: 143-155 (2010).