نوع مقاله : مقاله پژوهشی - کاربردی

نویسنده

دانشجوی دکتری مهندسی صنایع، دانشگاه جامع امام حسین (ع)، تهران، ایران.

10.22105/dmor.2021.235558.1156

چکیده

در نظر گرفتن سیاست­های نگهداری و تعمیرات (نت) در مدل­های مربوط به مسئله­ی زمان­بندی و تخصیص کارها به ماشین­آلات، علاوه بر سازگار‌کردن مدل­های ارائه شده با محیط­های تولیدی، سبب افزایش کارایی این مدل­ها در بهینه­سازی سیستم­های تولید می­شود. به همین منظور، در این مقاله یک مدل ریاضی جهت زمان­بندی ماشین­های موازی نامرتبط با هدف حداقل‌کردن مجموع وزنی زمان تکمیل کارها، توسعه داده شده است و در آن محدودیت عدم دسترسی به ماشین­آلات نیز منظور شده است. در این مدل وقفه در کارها مجاز در نظر گرفته شده و زمان‌های عدم دسترسی به ماشین­آلات، به دلیل اجرای برنامه­های نت پیشگیرانه و اضطراری، به زمان تکمیل کارها اضافه شده است. از آن جایی که مدل ارایه شده دارای پیچیدگی بالایی می­باشد، جهت حل آن از دو روش فراابتکاری الگوریتم ژنتیک و شبیه­سازی تبرید استفاده گردیده و عملکرد آن­ها با یکدیگر مورد مقایسه قرار گرفته است. نتایج نشان­دهنده­ی برتری روش شبیه­سازی تبرید نسبت به الگوریتم ژنتیک برای حل این مساله می­باشد.

کلیدواژه‌ها

موضوعات

عنوان مقاله [English]

Unrelated parallel-machine scheduling with preventive and emergency maintenance

نویسنده [English]

  • Saeed Khalili

Ph.D. Student of Industrial Engineering,, Imam Hossein Compressive University, Tehran, Iran.

چکیده [English]

Considering maintenance strategy in models which schedule and allocate jobs to machines, will make the proposed models compatible with production environments. Furthermore, this will cause higher model efficiency in optimizing the production systems. To this end, a mathematical model for scheduling unrelated parallel machines is developed to minimize total weighted completion times. Also in this approach, availability constraints have been considered, and preemption is allowed. Due to executing preventive maintenance and emergency maintenance programs, machine inaccessible times have been added to job completion times. Since the proposed model has high complexity, in order to solve the problem, two meta-heuristic methods including simulated annealing and genetic algorithm are used. In addition, their performances are compared to each other. The results indicate the superiority of simulated annealing over genetic algorithm for this particular problem.

کلیدواژه‌ها [English]

  • Unrelated parallel-machine scheduling
  • preventive and emergency maintenance
  • total weighted completion times
  • Metaheuristic Algorithms
Afrati, F., Bampis, E., Kenyon, C., & Milis, I. (2000). A PTAS for the average weighted completion time problem on unrelated machines. Journal of scheduling3(6), 323-332.
Aggoune, R. (2004). Minimizing the makespan for the flow shop scheduling problem with availability constraints. European journal of operational research153(3), 534-543.
Aggoune, R., & Portmann, M. C. (2006). Flow shop scheduling problem with limited machine availability: a heuristic approach. International journal of production economics99(1-2), 4-15.
Allaoui, H., & Artiba, A. (2006). Scheduling two-stage hybrid flow shop with availability constraints. Computers & operations research, 33(5), 1399-1419.
Azizoglu, M., & Kirca, O. (1999). On the minimization of total weighted flowtime with identical and uniform parallel machines. European journal of operational research, 113(1), 91-100.
Azizoglu, M., & Kirca, O. (1999b). Scheduling jobs on unrelated parallel machines to minimize regular total cost functions. IIE transactions, 31(2), 153-159.
Bagchi, T. P. (1999). Multiobjective scheduling by genetic algorithms. Springer.
Bank, M., Fatemi Ghomi, S., Jolai, F., & Behnamian, J. (2012). Application of particle swarm optimization and simulated annealing algorithms in flow shop scheduling problem under linear deterioration. Advances in engineering software, 47(1), 1-6.
Bruno, J., Coffman Jr, E. G., & Sethi, R. (1974). Scheduling independent tasks to reduce mean finishing time. Communications of the ACM17(7), 382-387.
Chen, Z.-L & Powell, W. B. (1999). Solving parallel machine scheduling problems by column generation. INFORMS journal on computing, 11(1), 78-94.
Cheng, R., Gen, M., & Tozawa, T. (1995). Minmax earliness/tardiness scheduling in identical parallel machine system using genetic algorithms. Computers & industrial engineering, 29(1), 513-517.
Chudak, F. A. (1999). A min‐sum 3/2‐approximation algorithm for scheduling unrelated parallel machines. Journal of Scheduling, 2(2), 73-77.
Cruz-Chávez, M. A., Juárez-Pérez, F., Ávila-Melgar, E. Y., & Martínez-Oropeza, A. (2009). Simulated annealing algorithm for the weighted unrelated parallel machines problem. 2009 electronics, robotics and automotive mechanics conference (CERMA). Cuernavaca, Mexico: IEEE. DOI: 10.1109/CERMA.2009.46
Das, K., Lashkari, R.,&Sengupta, S. (2007). Machine reliability and preventive maintenance planning for cellular manufacturing systems. European journal of operational research, 183(1), 162-180.
Fakhrzad, M. B., & Rajaei, B. (2017). Preventive maintenance in unrelated parallel machine scheduling with deterioration effect and setup times. Industrial management studies, 15(45), 1-43. (In Persian). https://journals.atu.ac.ir/article_7604.html
Gao, J., Gen, M., & Sun, L. (2006). Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm. Journal of intelligent manufacturing, 17(4), 493-507.
Gharbi, A., & Haouari, M. (2005). Optimal parallel machines scheduling with availability constraints. Discrete applied mathematics, 148(1), 63-87.
Hall, L. A., Schulz, A. S., Shmoys, D. B., &Wein, J. (1997). Scheduling to minimize average completion time: off-line and on-line approximation algorithms. Mathematics of operations research, 22(3), 513-544.
He, J., Li, Q., & Xu, D. (2016). Scheduling two parallel machines with machine-dependentavailabilities. Computers & operations research, 72, 31-42.
Hesam, A., Emami, S., & Nemati Keshteli, R. (2019). Scheduling of jobs and maintenance activities in an unrelated parallel machines environment. Journal of modeling in engineering, 17(58), 233-247.(In Persian). https://journals.semnan.ac.ir/article_4014.html
Jolai, F., Asefi, H., Rabiee, M., & Ramezani, P. (2013). Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem. Scientia Iranica, 20(3), 861-872. (In Persian). https://core.ac.uk/download/pdf/82523859.pd
Kirkpatrick, S. (1984). Optimization by simulated annealing: quantitative studies. Journal of statistical physics, 34(5-6), 975-986.
Lee, C.-Y. (1991). Parallel machines scheduling with nonsimultaneousmachine available time. Discrete applied mathematics, 30(1), 53-61.
Lee, J. Y., & Kim, Y. D. (2015). A branch and bound algorithm to minimize total tardiness of jobs in a two identical-parallel-machine scheduling problem with a machine availability constraint. Journal of the operational research society, 66(9), 1542-1554.
Lee, W. C., Wang, J. Y., & Lee, L. Y. (2015). A hybrid genetic algorithm for an identical parallel-machine problem with maintenance activity. Journal of the operational research society, 66(11), 1906-1918.
Lenstra, J. K., Rinnooy Kan, A., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of discrete mathematics, 1, 343-362.
Lin, Y., Pfund, M. E., & Fowler, J. W. (2011). Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problems. Computers & operations research, 38(6), 901-916.
Ma, Y., Chu, C., & Zuo, C. (2010). A survey of scheduling with deterministic machine availability constraints. Computers & industrial engineering, 58(2), 199-211.
McNaughton, R. (1959). Scheduling with deadlines and loss functions. Management science, 6(1), 1-12.
Noroozi, A., Mokhtari, H., & Kamal Abadi, I. N. (2013). Research on computational intelligence algorithms with adaptive learningapproach for scheduling problems with batch processing machines. Neurocomputing, 101, 190-203. (In Persian). https://dl.acm.org/doi/abs/10.1016/j.neucom.2012.08.011
Pinedo, M. (2001). Scheduling: theory, algorithms, and systems. Englewood Cliffs, N.J.: Prentice-Hall Inc.
Rezghi, A., & Rezaeian, J. (2018). Two stage assembly flow shop scheduling problem with preventive maintenance, aging effect and release time. Journal of industrial engineering, 52(1), 49-60. (In Persian). https://jieng.ut.ac.ir/article_66290.html
Rodriguez, F. J., Blum, C., García-Martínez, C., & Lozano, M. (2012). GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times. Annals of operations research, 201(1), 383-401.
Rodriguez, F. J., Lozano, M., Blum, C., & GarcíA-MartíNez, C. (2013). An iteratedgreedy algorithm for the large-scale unrelated parallel machines scheduling problem. Computers & operations research, 40(7), 1829-1841.
Schmidt, G. (1984). Scheduling on semi-identical processors. Zeitschrift für operations research, 28(5), 153-162.
Schulz, A. S., & Skutella, M. (2002). Scheduling unrelated machines by randomized rounding. SIAM journal on discrete mathematics, 15(4), 450-469.
Skutella, M. (2001). Convex quadratic and semidefinite programming relaxations in scheduling. Journal of the ACM (JACM), 48(2), 206-242.
Sortrakul, N., Nachtmann, H. L., & Cassady, C. R. (2005). Genetic algorithms for integrated preventive maintenance planning and production scheduling for a single machine. Computers in industry, 56(2), 161-168.
Sun, K., & Li, H. (2010). Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines. International journal of production economics, 124(1), 151-158.
Tan, Z., Chen, Y., & Zhang, A. (2013). On the exact bounds of SPT for scheduling on parallel machines with availability constraints. International journal of production economics, 146(1), 293-299.
Vahedi-Nouri, B., Fattahi, P., Rohaninejad, M., & Tavakkoli-Moghaddam, R. (2013). Minimizing the total completion time on a single machine with the learning effect and multiple availability constraints. Applied mathematical modelling, 37(5), 3126-3137.
Vredeveld, T., & Hurkens, C. (2002). Experimental comparison of approximation algorithms for scheduling unrelated parallel machines. INFORMS journal on computing, 14(2), 175-189.
Wang, X., & Cheng, T. (2015). A heuristic for scheduling jobs on two identical parallel machines with a machine availability constraint. International journal of production economics, 161, 74-82.
Xu, D., & Yang, D. L. (2013). Makespan minimization for two parallel machines scheduling with a periodic availability constraint: mathematical programming model, average-case analysis, and anomalies. Applied mathematical modelling, 37(15), 7561-7567.
Yang, S. J. (2013). Unrelated parallel-machine scheduling with deterioration effects and deteriorating multi-maintenance activities for minimizing the total completion time. Applied mathematical modelling, 37(5), 2995-3005.
Yang, X. S. (2010). Engineering optimization: an introduction with metaheuristic applications. John Wiley & Sons.
Yin, Y., Wang, Y., Cheng, T., Liu, W., & Li, J. (2017). Parallel-machine scheduling of deteriorating jobs with potential machine disruptions. Omega, 69, 17-28.
Zhao, C.,Ji, M., & Tang, H. (2011). Parallel-machine scheduling with an availability constraint. Computers & industrial engineering, 61(3), 778-781.