A Heuristic Algorithm for Solving Single Machine Scheduling Problem with Periodic Maintenance
Subject Areas : Business StrategyAmir Ebrahimi Zade 1 , Mohammad Bagher Fakhrzad 2 , Mohsen Hasaninezhad 3
1 - Department of Industrial Engineering,
Yazd University, Yazd, Iran
2 - Department of Industrial Engineering,
Yazd University, Yazd, Iran
3 - Department of Industrial Engineering,
Iran University of Science and Technology, Tehran, Iran
Keywords: Keywords: Single Machine Scheduling, Periodic Maintenance, Nonresumable Jobs, Mathematical Formulation, heuristic algorithm,
Abstract :
Abstract. In this paper, the scheduling problem with nonresumable jobs and maintenance process is considered in order to minimize the makespan under two alternative strategies. The first strategy is to implement the maintenance process on the machine after a predetermined time period and the second one is to consider the maximum number of jobs that can be done with an especial tool. We propose a new mathematical formulation for the aforementioned problem and regarding the problem is included in the NP-Hard class of problems, in the second part of the paper, we propose a heuristic algorithm in order to solve the problem in a reasonable time. Also we compare the performance of the proposed algorithm with existing methods in the literature. Computational results showed that the proposed algorithm is able to attain optimum solutions in most cases and also corroborate its better performance than the existing heuristic methods in the literature.
[1] Pinedo, M.L. (2002). Scheduling: Theory, Algorithms, and Systems (Vol. 1) New Jersey: Springer.
[2] Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. Rinnooy. (1979). Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey. In E. L. J. P.L. Hammer & B. H. Korte (Eds.), Annals of Discrete Mathematics; 5: 287-326.
[3] Pinedo, M., Rammouz, E. (1988). A note on stochastic scheduling on a single machine subject to breakdown and repair. Probability in the Engineering and Information- National Sciences; 2:41–9.
[4] Birge, J., Frenk, JBG, Mittenthal, J., Rinnooy Kan, AHG. (1990). Single-machine scheduling subject to stochastic breakdowns. Naval Research Logistics; 37:664–77.
[5] Frostig, E. (1991). A note on stochastic scheduling on a single machine subject to breakdown-the preemptive repeat model. Probability, Engineering and Informational Sciences; 5:349–54.
[6] Adiri, I., Bruno, J., Frostig, E., Rinnooy Kan, AHG. (1989). Single machine flow-time scheduling with a single breakdown. Acta Informatica; 26:679–96.
[7] Adiri, I., Frostig, E., Rinnooy Kan, AHG. (1991). Scheduling on a single machine with a single breakdown to minimize stochastically the number of tardy jobs. Naval Research Logistics; 38:261–71.
[8] Akturk, MS., Ghosh, JB., Gunes, ED. (2003). Scheduling with tool changes to minimize total completion time: a study of heuristics and their performance. Naval Research Logistics; 50:15–30.
[9] Akturk, MS., Ghosh, JB., Gunes ED. (2004). Scheduling with tool changes to minimize total completion time: basic results and SPT performance. European Journal of Operations Research; 157:784–90.
[10] Ecker, KH. Gupta, JND. (2005). Scheduling tasks on a flexible manufacturing machine to minimize tool change delays. European Journal of Operations Research; 164:627–38.
[11] Chen, JS. (2008). Optimization models for the tool change scheduling problem. Omega; 36:888–94.
[12] Choi, Y-C., Kim, Y-D. (2001). Tool replacement policies for a machining center producing multiple types of products with distinct due dates. International Journal of Production Research; 39:907–21.
[13] Yang, D.L., Hung, C.L., Hsu, C.J., Chern, M.S., (2002). Minimizing the makespan in a single machine scheduling problem with a flexible maintenance. Journal of the Chinese Institute of Industrial Engineers; 19: 63–66.
[14] Qi, X., Chen, T., Tu. F. (1999). Scheduling the maintenance on a single machine. Journal of the Operational Research Society; 50:1071–8.
[15] Chen, JS. (2006). Single machine scheduling with flexible and periodic maintenance. Journal of the Operational Research Society; 57:703–10.
[16] Low, C., Ji, M., Hsu, C-J., Su, C-T. (2010). Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance. Applied Mathematical Modeling; 34: 334–42.
[17] Liao, CJ. Chen, WJ. (2003). Single-machine scheduling with periodic maintenance and nonresumable jobs. Computers and Operations Research; 30:1335–47.
[18] Chen, WJ. (2006). Minimizing total flow time in the single machine scheduling problem with periodic maintenance. Journal of the Operational Research Society; 57:410 –5.
[19] Chen, WJ. (2009). Minimizing number of tardy jobs on a single machine subject to periodic maintenance. Omega; 37:591–9.
[20] Lee, S-H., Lee, I-G. (2008). Heuristic algorithm for the single machine scheduling with periodic maintenance. Journal of the Korean Institute of Industrial Engineers; 34:318–27.
[21] Lau, HC. Zhang, C. (2004). Job scheduling with unfixed availability constraints. In: Proceedings of 35th Meeting of the Decision Sciences Institute. Boston, USA; p. 4401–6.
[22] Liao, C-J., Chen, C-M., Lin, C-H. (2007). Minimizing makespan for two parallel machines with job limit on each availability interval. Journal of the Operational Research Society 58 938–47.
[23] Dell’ Amico, M., Martello, S. (2001). Bounds for the cardinality constrained P||Cmax problem. Journal of Scheduling 4:123–38.
[24] Yang, D-L., Hsu, C-J., Kuo, W-H. (2008). A two-machine flow shop scheduling problem with a separated maintenance constraint. Computers & Operations Research 35:876–83.
[25] Hsu, C-J., Low, C., Su, C-T., (2010). A single-machine scheduling problem with maintenance activities to minimize makespan. Applied Mathematics and Computation 215: 3929–3935.
[26] Pinedo, M. (1995). Scheduling: theory, algorithms and systems. New Jersey: Prentice-Hall.
[27] Lee, C.Y., Liman, S.D. (1992). Single machine flow-time scheduling with scheduled maintenance. Acta Informatica 29, 375–382.