A genetic algorithm for preemptive scheduling of a single machine

Abstract: This paper presents a mathematical model for scheduling of a single machine when there are preemptions in jobs. The primary objective of the study is to minimize different objectives such as earliness, tardiness and work in process. The proposed mathematical problem is considered as NP-Hard and the optimal solution is available for small scale problems. Therefore, a genetic algorithm (GA) is developed to solve the problem for large-scale problems. The implementation of the proposed model is compared with GA for problems with up to 50 jobs using three methods of roulette wheel sampling, random sampling and competition sampling. The results have indicated that competition sampling has reached optimal solutions for small scale problems and it could obtain better near-optimal solutions in relatively lower running time compared with other sampling methods.

How to cite this paper

 Golmohammadi, A., Bani-Asadi, H., Zanjani, H & Tikani, H. (2016). A genetic algorithm for preemptive scheduling of a single machine.International Journal of Industrial Engineering Computations , 7(4), 607-614.

Refrences

Ahmadizar, F., & Farhadi, S. (2015). Single-machine batch delivery scheduling with job release dates, due windows and earliness, tardiness, holding and delivery costs. Computers & Operations Research, 53, 194-205.
Bülbül, K., Kaminsky, P., & Yano, C. (2007). Preemption in single machine earliness/tardiness scheduling. Journal of Scheduling, 10(4-5), 271-292.
Davis, J. S., & Kanet, J. J. (1993). Single‐machine scheduling with early and tardy completion costs. Naval Research Logistics (NRL), 40(1), 85-101.
Hendel, Y., Runge, N., & Sourd, F. (2009). The one-machine just-in-time scheduling problem with preemption. Discrete Optimization, 6(1), 10-22.
Holland, J., (1992). Adaptation in natural and artificial systems: MIT Press. Cambridge, MA.
Kazemi, M., Nikoofarid, E., Aalaei, A., & Kia, R. (2012). Just-in-time preemptive single machine problem with costs of earliness/tardiness, interruption and work-in-process. International Journal of Industrial Engineering Computations, 3(3), 321-336.
Khorshidian, H., Javadian, N., Zandieh, M., Rezaeian, J., & Rahmani, K. (2011). A genetic algorithm for JIT single machine scheduling with preemption and machine idle time. Expert Systems with Applications, 38(7), 7911-7918.
Lenstra, J. K., Kan, A. R., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343-362.
Liao, C. J., & Cheng, C. C. (2007). A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date. Computers & Industrial Engineering, 52(4), 404-413.
M’Hallah, R. (2007). Minimizing total earliness and tardiness on a single machine using a hybrid heuristic. Computers & Operations Research, 34(10), 3126-3142.
Montgomery, D. C. (2008). Design and analysis of experiments. John Wiley & Sons.
Runge, N., & Sourd, F. (2009). A new model for the preemptive earliness–tardiness scheduling problem. Computers & Operations Research, 36(7), 2242-2249.
Sourd, F., & Kedad-Sidhoum, S. (2003). The one-machine problem with earliness and tardiness penalties. Journal of scheduling, 6(6), 533-549.
Sun, X., Noble, J. S., & Klein, C. M. (1999). Single-machine scheduling with sequence dependent setup to minimize total weighted squared tardiness. IIE transactions, 31(2), 113-124.
Szwarc, W., & Mukhopadhyay, S. K. (1996). Earliness and tardiness single machine scheduling with proportional weights. Journal of Global Optimization, 9(3-4), 227-238.
Valente, J. M. (2008). An exact approach for the single machine scheduling problem with linear early and quadratic tardy penalties. Asia-Pacific Journal of Operational Research, 25(02), 169-186.
Valente, J. M., & Gonçalves, J. F. (2009). A genetic algorithm approach for the single machine scheduling problem with linear earliness and quadratic tardiness penalties. Computers & Operations Research, 36(10), 2707-2715.
Wang, X. R., Huang, X., & Wang, J. B. (2011). Single-machine scheduling with linear decreasing deterioration to minimize earliness penalties. Applied Mathematical Modelling, 35(7), 3509-3515.