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 which is included in the NP-Hard class of problems; in the second part of the paper, we propose a dynamic genetic algorithm so that the large- and medium-scale problems could be solvable in computationally reasonable time. Also we compare the performance of the proposed algorithm with existing methods in the literature. Experimental results showed that the proposed genetic algorithm is able to attain optimum solutions in most cases and also corroborate its better performance from the existing heuristic methods in the literature. 1. Introduction and Literature Review In most scheduling problems, it is assumed that the machine is continuously and uninterruptedly available. However, in the real world problems this is not the case (Pinedo [1]). The possible machine breakdown and interruption would be unavoidable in case of working continuously and also this may affect the quality of the jobs being processed by the machine. Thus, the periodic preventive maintenance process is usually planned and implemented to avoid the aforementioned problem. In this paper the scheduling problem is mathematically formulated subject to the amount of time the machine is available between the two consecutive periods, at the end of which the maintenance process is implemented and the maximum number of jobs which could be processed by the machine over the operating time. Jobs are done in two different ways when we have a limited time period in which the machine is available before the next maintenance process. In the first case, which is called preemptive jobs, it is assumed that operations of the in-process jobs could be continued after machine interruption. On the other hand, for nonpreemptive jobs, it is assumed that the incomplete jobs must be reprocessed after interruption. Also, for some manufacturing processes such as manufacturing of the electronic circuits, the number of jobs to process before changing the tools is a constraint. Considering Graham’s three-field notation for symbolizing the scheduling problems, this case is specified with 1/nr-pm/ (Graham et al. [2]). The problem of machine availability has been widely considered in the
References
[1]
M. Pinedo, Scheduling: Theory, Algorithms and Systems, Prentice Hall, Upper Saddle River, NJ, USA, 2002.
[2]
R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. R. Kan, “Optimization and approximation in deterministic sequencing and scheduling: a survey,” Annals of Discrete Mathematics, vol. 5, pp. 287–326, 1979.
[3]
M. Pinedo and E. Rammouz, “A note on stochastic scheduling on a single machine subject to breakdown and repair,” Probability in the Engineering and Informational Sciences, vol. 2, pp. 41–49, 1988.
[4]
J. Birge, J. B. G. Frenk, J. Mittenthal, and A. H. G. R. Khan, “Single-machine scheduling subject to stochastic breakdowns,” Naval Research Logistics, vol. 37, no. 5, pp. 661–677, 1990.
[5]
E. Frostig, “A note on stochastic scheduling on a single machine subject to breakdown-the preemptive repeat model,” Probability in the Engineering and Informational Sciences, vol. 5, pp. 349–354, 1991.
[6]
I. Adiri, J. Bruno, E. Frostig, and A. H. G. R. Kan, “Single machine flow-time scheduling with a single breakdown,” Acta Informatica, vol. 26, no. 7, pp. 679–696, 1989.
[7]
I. Adiri, E. Frostig, and A. H. G. R. Kan, “Scheduling on a single machine with a single breakdown to minimize stochastically the number of tardy jobs,” Naval Research Logistics, vol. 38, no. 2, pp. 261–271, 1991.
[8]
M. S. Akturk, J. B. Ghosh, and E. D. Gunes, “Scheduling with tool changes to minimize total completion time: a study of heuristics and their performance,” Naval Research Logistics, vol. 50, no. 1, pp. 15–30, 2003.
[9]
M. S. Akturk, J. B. Ghosh, and E. D. Gunes, “Scheduling with tool changes to minimize total completion time: basic results and SPT performance,” European Journal of Operational Research, vol. 157, no. 3, pp. 784–790, 2004.
[10]
K. H. Ecker and J. N. D. Gupta, “Scheduling tasks on a flexible manufacturing machine to minimize tool change delays,” European Journal of Operational Research, vol. 164, no. 3, pp. 627–638, 2005.
[11]
J. S. Chen, “Optimization models for the tool change scheduling problem,” Omega, vol. 36, no. 5, pp. 888–894, 2008.
[12]
Y. C. Choi and Y. D. Kim, “Tool replacement policies for a machining centre producing multiple types of products with distinct due dates,” International Journal of Production Research, vol. 39, no. 5, pp. 907–921, 2001.
[13]
D. L. Yang, C. L. Hung, C. J. Hsu, and M. S. Chem, “Minimizing the makespan in a single machine scheduling problem with a flexible maintenance,” Journal of the Chinese Institute of Industrial Engineers, vol. 19, no. 1, pp. 63–66, 2002.
[14]
X. Qi, T. Chen, and F. Tu, “Scheduling the maintenance on a single machine,” Journal of the Operational Research Society, vol. 50, no. 10, pp. 1071–1078, 1999.
[15]
J. S. Chen, “Single-machine scheduling with flexible and periodic maintenance,” Journal of the Operational Research Society, vol. 57, no. 6, pp. 703–710, 2006.
[16]
C. Low, M. Ji, C. J. Hsu, and C. T. Su, “Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance,” Applied Mathematical Modelling, vol. 34, no. 2, pp. 334–342, 2010.
[17]
C. Low, C. J. Hsu, and C. T. Su, “A modified particle swarm optimization algorithm for a single-machine scheduling problem with periodic maintenance,” Expert Systems with Applications, vol. 37, no. 9, pp. 6429–6434, 2010.
[18]
C. J. Liao and W. J. Chen, “Single-machine scheduling with periodic maintenance and nonresumable jobs,” Computers and Operations Research, vol. 30, no. 9, pp. 1335–1347, 2003.
[19]
W. J. Chen, “Minimizing total flow time in the single-machine scheduling problem with periodic maintenance,” Journal of the Operational Research Society, vol. 57, no. 4, pp. 410–415, 2006.
[20]
W. J. Chen, “Minimizing number of tardy jobs on a single machine subject to periodic maintenance,” Omega, vol. 37, no. 3, pp. 591–599, 2009.
[21]
S. H. Lee and I. G. Lee, “Heuristic algorithm for the single machine scheduling with periodic maintenance,” Journal of the Korean Institute of Industrial Engineers, vol. 34, pp. 318–327, 2008.
[22]
H. C. Lau and C. Zhang, “Job scheduling with unfixed availability constraints,” in Proceedings of the 35th Meeting of the Decision Sciences Institute, pp. 4401–4406, Boston, Mass, USA, 2004.
[23]
C. J. Liao, C. M. Chen, and C. H. Lin, “Minimizing makespan for two parallel machines with job limit on each availability interval,” Journal of the Operational Research Society, vol. 58, no. 7, pp. 938–947, 2007.
[24]
M. Dell'Amico and S. Martello, “Bounds for the cardinality constrained P∥Cmax problem,” Journal of Scheduling, vol. 4, no. 3, pp. 123–138, 2001.
[25]
D. L. Yang, C. J. Hsu, and W. H. Kuo, “A two-machine flowshop scheduling problem with a separated maintenance constraint,” Computers and Operations Research, vol. 35, no. 3, pp. 876–883, 2008.
[26]
C. J. Hsu, C. Low, and C. T. Su, “A single-machine scheduling problem with maintenance activities to minimize makespan,” Applied Mathematics and Computation, vol. 215, no. 11, pp. 3929–3935, 2010.
[27]
C. Y. Lee and S. D. Liman, “Single machine flow-time scheduling with scheduled maintenance,” Acta Informatica, vol. 29, no. 4, pp. 375–382, 1992.
[28]
J. H. Holland, Adaptation in Natural and Artificial System, University of Michigan Press, Ann Arbor, Mich, USA, 1975.
[29]
L. Davis, Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, NY, USA, 1991.
[30]
D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, New York, NY, USA, 1989.
[31]
T. Back, D. Fogel, and Z. Michalawecz, Handbook of Evolutionary Computation, Oxford University Press, Oxford, UK, 1997.
[32]
M. Obitko, “Introduction to genetic algorithms,” 1998, http://www.obitko.com/tutorials/genetic-algorithms.
[33]
G. Syswerda, “uniform crossover in genetic algorithms,” in Proceedings of the 3rd International Conference on Genetic Algorithms, pp. 2–9, 1989.
[34]
A. Hamidinia, S. Khakabimamaghani, M. M. Mazdeh, and M. Jafari, “A genetic algorithm for minimizing total tardiness/earliness of weighted jobs in a batched delivery system,” Computers and Industrial Engineering, vol. 62, no. 1, pp. 29–38, 2012.
