Abstract
In this paper, we study a single machine scheduling problem with deteriorating processing time of jobs and multiple preventive maintenances which reset deteriorated processing time to the original processing time. In this situation, we consider three kinds of problems whose performance measures are makespan, total completion time, and total weighted completion time. First, we formulate integer programming formulations, and using the formulations, one can find optimal solutions for small problems. Since these problems are known to be NP-hard and the size of real problem is very large, we propose a number of heuristics and design genetic algorithms for the problems. Finally, we conduct some computational experiments to evaluate the performance of the proposed algorithms.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bachman A, Janiak A, Kovalyov MY (2002) Minimizing the total weighted completion time of deteriorating jobs. Inf Process Lett 81(2):81–84
Browne S, Yechiali U (1990) Scheduling deteriorating jobs on a single processor. Oper Res 38:495–498
Cassady CR, Kutanoglu E (2005) Integrating preventive maintenance planning and production scheduling for a single machine. IEEE Trans Reliab 54(2):304–309
Cheng TCE, Ding Q (2000) Single machine scheduling with deadlines and increasing rates of processing times. Acta Informatica 36:673–692
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco
Gen M, Cheng R (1997) Genetic algorithms and engineering design. Wiley, New York
Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, New York
Graham RL, Lawler EL, Lenstra JK, Rinnooy KAHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287–326
Graves GH, Lee CY (1999) Scheduling maintenance and semiresumable jobs on a single machine. Nav Res Logist 46:845–863
Gupta JND, Gupta SK (1988) Single facility scheduling with nonlinear processing times. Comput Ind Eng 14:387–393
Kovalyov YM, Kubiak W (1998) A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs. Journal of Heuristics 3:287–297
Kubiak W, Vende S (1998) Scheduling deteriorating jobs to minimize makespan. Nav Res Logist 45:511–523
Kunnathur AS, Gupta SK (1990) Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem. Eur J Oper Res 47:56–64
Lee CY, Chen ZL (2000) Scheduling of jobs and maintenance activities on parallel machines. Nav Res Logist 47:61–67
Lee CY, Lin CS (2001) Single-machine scheduling with maintenance and repair rate-modifying activities. Eur J Oper Res 135:493–513
Lee CY, Leon VJ (2001) Machine scheduling with a rate-modifying activity. Eur J Oper Res 128:119–128
Lodree EJ, Geiger CD (2009) A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration. Eur J Oper Res 201(2):644–648
Mosheiov G (1991) V-shaped polices to scheduling deteriorating jobs. Operation Research 39:979–991
Mosheiov G (1995) Scheduling jobs with step-deterioration: minimizing makespan on a single- and multi-machine. Comput Ind Eng 28:869–879
Ozturkoglu Y, Bulfin R (2011) A unique integer mathematical model for scheduling deteriorating jobs with rate-modifying activities on a single machine. Int J Adv Manuf Technol 57:753–762
Ozturkoglu Y, Bulfin R (2012) Scheduling jobs to consider physiological factors. Human factors and ergonomics in manufacturing & service industries. Wiley, New York, pp 113–120, 22 (2)
Qi X, Chen T, Tu F (1999) Scheduling the maintenance on a single machine. J Oper Res Soc 50:1071–1078
Sortrakul N, Nachtmann CR, Cassady CR (2005) Genetic algorithms for integrated preventive maintenance planning and production scheduling for a single machine. Computers In Industry 56:161–168
Wang CS, Uzsoy R (2002) A genetic algorithm to minimize maximum lateness on a batch processing machine. Comput Oper Res 29:1621–1640
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Kim, B.S., Ozturkoglu, Y. Scheduling a single machine with multiple preventive maintenance activities and position-based deteriorations using genetic algorithms. Int J Adv Manuf Technol 67, 1127–1137 (2013). https://doi.org/10.1007/s00170-012-4553-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-012-4553-x