Abstract
In this paper, we consider the problem of scheduling a set of M preventive maintenance tasks to be performed on M machines. The machines are assigned to execute production tasks. We aim to minimize the total preventive maintenance cost such that the maintenance tasks have to continuously be run during the schedule horizon. Such a constraint holds when the maintenance resources are not sufficient. We solve the problem by two exact methods and meta-heuristic algorithms. As exact procedures we used linear programming and branch and bound methods. As meta-heuristics, we propose a local search approach as well as a genetic algorithm. Computational experiments are performed on randomly generated instances to show that the proposed methods produce appropriate solutions for the problem. The computational results show that the deviation of the meta-heuristics solutions to the optimal one is very small, which confirms the effectiveness of meta-heuristics as new approaches for solving hard scheduling problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abdul-Razaq T., Potts C. N. (1988) Dynamic state space relaxation for single machine scheduling. Journal of Operations Research Society 39(2): 141–152
Aghezzaf E. H., Jamali M. A., Ait-Kadi D. (2007) An integrated production and preventive maintenance planning model. European Journal of Operational Research 181: 679–685
Aghezzaf, E. H., & Najid, N. M. (2008). Integrated production planning and preventive maintenance in deteriorating production systems. Information Sciences, 178, 3382–3392.
Azizoglu M., Kondakci S., Kirca O. (1991) Bicriteria scheduling problem involving total tardiness and total earliness penalties. International Journal of Production Economics 23: 17–24
Baker K. R., Scudder G. D. (1990) Sequencing with earliness and tardiness penalties: a review. Operations Research 38: 22–36
Graves H. G., Lee C.-Y. (1999) Scheduling maintenance and semiresumable jobs on a single machine. Naval Research Logistics 46: 845–863
Held M., Karp R. M. (1962) A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics 10: 196–210
Kacem I. (2007) Lower bounds for tardiness minimization on a single machine with family setup times. International Journal of Operations Research 4: 18–31
Kubiak W., Blazewicz J., Formanowicz P., Breit J., Schmidt G. (2002) Two-machine flow shops with limited machine availability. European Journal of Operational Research 136: 528–540
Lee C.-Y. (1996) Minimising the makespan in the two machine scheduling scheduling problem with an availability constraint. Operational Research Letters 20: 129–139
Lee C.-Y., Chen Z.-L. (2000) Scheduling jobs and maintenance activities on parallel machines. Naval Research Logistics 47: 145–165
Li G. (1997) Single machine earliness and tardiness scheduling. European Journal of Operational Research 26: 546–558
Liaw C.-F. (1999) A branch and bound algorithm for the single machine earliness and tardiness scheduling problem. Computers & Operations Research 26: 679–693
M’Halla R. (2006) Minimising total earliness and tardiness on a single machine using a hybrid heuristic. Computers & Operation Research 34: 3126–3142
Ow P. S., Morton E. T. (1989) The single machine early/tardy problem. Management Science 35: 331–342
Potts C. N., Van Wassenhove L. N. (1984) A branch and bound algorithm for the total weighted tardiness problem. Operations Research 33: 363–377
Sakib A. M., Anup K. S. (2001) Single machine weighted earliness/tardiness penalty problem with a common due date. Computers & Operation Research 28: 649–669
Sourd F., Keded-Sidhoum S., Rio Solis Y. (2008) Lower bounds for the earliness–tardiness scheduling problem on parallel machines with distinct due dates. European Journal of Operational Research 189: 1305–1319
Smith W. E. (1956) Various optimizers for single-stage production. Naval Research Logistics Quarterly 3: 59–66
Van den Akker M., Hoogeveen J. A., van deVelde S. (2002) Combining column generation and lagrangean relaxation to solve a single-machine common due date problem. INFORMS Journal on Computing 14: 37–51
Valente J. M. S., Shaller J. E. (2010) Improved heuristics for the single machine scheduling problem with linear early and quadratic tardy penalties. European Journal of Industrial Engineering 4: 99–129
Valente J. M. S. (2010) Heuristics for the single machine scheduling problem with early and quadratic tardy penalties. European Journal Industrial Engineering 4: 431–448
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Rebai, M., Kacem, I. & Adjallah, K.H. Earliness–tardiness minimization on a single machine to schedule preventive maintenance tasks: metaheuristic and exact methods. J Intell Manuf 23, 1207–1224 (2012). https://doi.org/10.1007/s10845-010-0425-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10845-010-0425-0