Bi-objective optimization algorithms for joint production and maintenance scheduling: application to the parallel machine problem
Tóm tắt
This paper deals with the joint production and maintenance scheduling problem according to a new bi-objective approach. This method allows the decision maker to find compromise solutions between the production objectives and maintenance ones. Reliability models are used to take into account the maintenance aspect of the problem. The aim is to simultaneously optimize two criteria: the minimization of the makespan for the production part and the minimization of the system unavailability for the maintenance side. Two decisions are taken at the same time: finding the best assignment of n jobs to m machines in order to minimize the makespan and deciding when to carry out the preventive maintenance actions in order to minimize the system unavailability. The maintenance actions numbers as well as the maintenance intervals are not fixed in advance. Two evolutionary genetic algorithms are compared to find an approximation of the Pareto-optimal front in the parallel machine case. On a large number of test instances (more than 5000), the obtained results are promising.
Tài liệu tham khảo
Adzapka K.P., Adjallah K.H., Yalaoui F. (2004) On-line maintenance job scheduling and assignment to resources in distributed systems by heuristic-based optimization. Journal of intelligent manufacturing 15: 131–140
Amodeo, L., Chen, H., & El-Hadji, A. (2007). Multi-objective supply chain optimization: An industrial case study (pp. 732–741). Springer-Verlag, EvoWorkshops, LNCS 4448.
Barichard, V. (2005). Hybrid approaches for multiobjective problems. PhD thesis, Doctoral School of Angers, France (in French).
Basseur, M. (2005). Design of cooperative algorithms for multiobjective optimization: Application to Flowshop scheduling problems. PhD thesis, University of Sciences and Technologies of Lille, France (in French).
Cassady C.R., Kutanoglu E. (2003) Minimizing job tardiness using integrated preventive maintenance planning and production scheduling. IIE Transactions 35: 503–513
Coellom, C. A., & Cortes, N. C. (2002). Solving multi-objective optimization problems using an artificial immune system. Evolutionary Computation Group, Instituto Politécnico Nacional No. 2508 Col. San Pedro Zacatenco México.
Deb, K., Agrawal, S., Pratab, A., & Meyarivan, T. (2000). A fast elitist non dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. KanGAL report 200001, Indian Institute of Technology, Kanpur, India.
Ebeling C.E. (1997) An introduction to reliability and maintainability engineering. McGraw-Hill, USA
Fleischer M. (2003) The measure of Pareto optima, applications to the multi-objective metaheuristics. Lecture Notes in Computer Science, Springer (EMO’ 03 2632: 519–533
Garey M.R., Johnson D.S (1979) Computers and Intractability: A guide to the theory of NP-Completeness. California, San Francisco, W.H., Freeman and Company
Gaspar-Cunta A., Covas J.A. (2003) A real-word test problem for EMO algorithms. Lecture Notes in Computer Science, Springer 2632: 752–766
Ishibuchi H., Yoshida T., Murata T. (2003) Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation 7(2): 204–223
Kaabi, J., Varnier, C., & Zerhouni, N. (2002). Heuristics for scheduling maintenance and production on a single machine. IEEE Conference on Systems, Man and Cybernetics. October 6–9 Hammamet, Tunisia.
Kaabi, J., Varnier, C., & Zerhouni, N. (2003). Genetic algorithm for scheduling production and maintenance in a Flow Shop. Laboratory of automatic of Besançon, France (in French).
Kaspi, M., & Montreuil, B. (1988). On the scheduling of identical parallel processes with arbitrary initial processor available time. Technical report, School of Industrial Engineering, Purdue University.
Knowles, J., & Corne, D. (2002). On metrics for comparing nondominated sets. Proceedings of the 2002 Congress on Evolutionary Computation (CEC 2002), IEEE, pp. 711–716.
Knowles, J., & Hughes, E. J. (2005). Multi-objective optimization on a budget of 250 evaluations. School of Chemistry, University of Manchester UK.
Landa-Silva, J. D., Burke, E. K., & Petrovic, S. (2003). An Introduction to multi-objective metaheuristics for scheduling and timetabling. Automated Scheduling, Optimisation and Planning Research Group, School of Computer Science and IT, University of Nottingham, UK.
Lee C.-Y. (1991) Parallel machine scheduling with non simultaneous machine available time. Discrete and Applied Mathematics 30: 53–61
Lee C.-Y. (1996) Machine scheduling with an availability constraint. Journal of Global Optimization 9: 395–416
Lee C.-Y., Chen Z.L. (2000) Scheduling jobs and maintenance activities on parallel machines. Naval Research Logistics 47-2: 145–165
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(7): 938–947
Liao C.-J., Shyur D.-L., Lin C.-H. (2005) Makespan minimization for two parallel machines with an availability constraint. European Journal of Operational Research 160: 445–456
Liman, S. D. (1991). Scheduling with capacities and due-dates. PhD thesis, Industrial and Systems Engineering Department, University of Florida, USA.
Mellouli, R., Sadfi, C., Kacem, I., & Chu, C. (2006). Scheduling on parallel machines with availability constraints. Sixth International Francophone Conference of Modeling and Simulation, Mosim’06, Marocco (in French).
Mosheiv G. (1994) Minimizing the sum of job completion times on capacitated parallel machines. Mathematical and Computer Modeling 20: 91–99
Ruiz R., García-Diaz J.C., Maroto C. (2007) Considering scheduling and preventive maintenance in the flowshop sequencing problem. Computers & Operations Research 34(11): 3314–3330
Schmidt G. (1984) Scheduling on semi-identical processors. Zeitschrift fur Operation Research 28: 153–162
Schmidt G. (2000) Scheduling with limited machine availability. European Journal of Operational Research 121: 1–15
Velasco, N., Dejax, P., Guéret, C., & Prins, C. (2006). Genetic algorithm for the bi objective collection and delivery problem. Sixth International Francophone Conference of Modeling and Simulation, Mosim’06, Marocco.
Vilcot, G., Billaut, J.-C., Esswein, C. (2006). A genetic algorithm for a bi-criteria flexible job shop scheduling problem. IEEE International Conference on Service Systems and Service Management (ICSSSM’06).
Villemeur A. (1991) Reliability, availability, maintainability and safety assessment. Wiley, USA
Weinstein L., Chung C.-H. (1999) Integrated maintenance and production decisions in hierarchical production planning environment. Computers and Operations Research 26: 1059–1074
Xu D., Sun K., Li H. (2008) Parallel machine scheduling with almost periodic non-preemptive maintenance and jobs to minimize makespan. Computers and Operations Research 35: 1344–1349
Zitzler, E. (1999). Evolutionary algorithms for multi-objective optimization: Methods and applications. PhD thesis, Swiss Federal Institute of Technology, Zurich.
Zydallis, J. B. (2003). Explicit building-block multi-objective genetic algorithms: Theory, analysis, and development. PhD dissertation, Air Force Institute of Technology, Ohio.