A Mixed Integer Model for Unrelated Parallel Machine Scheduling with Job Deteriorating Effect

Document Type : Original Research Article


School of Industrial Engineering, College of Engineering, Tehran University, Tehran, Iran


Maintenance planning has been widely applied in manufacturing systems to improve production efficiency. In some real cases, job processing times may change over time, but they are mostly assumed to be constant in the scheduling literature. Hence, in this article, a mixed integer model is developed to optimize scheduling jobs on unrelated parallel machines with reliability-based maintenance and job deteriorating effects. The proposed model considers a reliability-based maintenance system and multi-stage quality cost and starts a time-dependent deteriorating effect. Based on the assumptions, if machines work in undesirable conditions, quality reduction and quality cost increment would occur. According to the start time-dependent deteriorating effect, the processing time of each job is a function of its start time. The problem is modeled by an integer linear programming method. Computational experiments are performed on various numerical instances to show the model’s effectiveness.


Main Subjects

[1]     E. Vallada, andR. Ruiz. "A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times". European Journal of Operational Research, vol. 211, no. 3): p. 612-622, 2011.
[2]     D.W.Kim, D.G.Na, and F. Frank Chen, "Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective". Robotics and Computer-Integrated Manufacturing, vol. 19, no. 1, p. 173-181, 2003.
[3]     C.O.Kim, and H.J. Shin, "Scheduling jobs on parallel machines: a restricted tabu search approach". The International Journal of Advanced Manufacturing Technology, vol. 22, no. 3-4, p. 278-287, 2003.
[4]     J.F. Chen, "Unrelated parallel machine scheduling with secondary resource constraints". The International Journal of Advanced Manufacturing Technology, vol. 26, no. 3, p. 285-292, 2005.
[5]     J.F.Chen, and T.H. Wu, "Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints". Omega, vol. 34, no. 1, p. 81-89, 2006.
[6]     V.Kayvanfar, G. Komaki, A.Aalaei, and M.Zandieh, "Minimizing total tardiness and earliness on unrelated parallel machines with controllable processing times". Computers & Operations Research, vol. 41, p. 31-43, 2014.
[7]     A.Berthier, A.Yalaoui,H.Chehade,F.Yalaoui, L. Amodeo, and C.Bouillot, “Unrelated parallel machines scheduling with dependent setup times in textile industry”. Computers & Industrial Engineering, 2022, ISSN 0360-8352, https://doi.org/10.1016/j.cie.2022.108736.
[8]     M.A.A. Al-qaness, A.A.Ewees, and M. AbdElaziz, “Modified whale optimization algorithm for solving unrelated parallel machine scheduling problems”. Soft Computing,vol. 25: p. 9545–9557, 2021.
[9]     M.Sheikhalishahi,N. Eskandari,A.Mashayekhi, and A.Azadeh, “Multi-objective open shop scheduling by considering human error and preventive maintenance”. Applied Mathematical Modelling, vol. 67: p. 573-587, 2019.
[10]  G.Schmidt, "Scheduling with limited machine availability". European Journal of Operational Research, vol. 121, no. 1, p. 1-15, 2000.
[11]  I.Adiri, J.Bruno, E.Frostig, andA.R.Kan, "Single machine flow-time scheduling with a single breakdown". ActaInformatica, vol. 26, no. 7, p. 679-696. 1989.
[12]  C.Y. Lee,andS.D.Liman, “Single machine flow-time scheduling with scheduled maintenance”. ActaInformatica, vol. 29, no. 4, p. 375-382, 1992.
[13]  C.Y.Lee, and Z.L. Chen, "Scheduling jobs and maintenance activities on parallel machines". Naval Research Logistics, vol. 47, no. 2, p. 145-165, 2000.
[14]  K.Linderman, K.E.McKone-Sweet, and Anderson, J. C., "An integrated systems approach to process control and maintenance". European Journal of Operational Research, 164(2): pp. 324-340, 2005.
[15]  S.Panagiotidou, and G.Tagaras, "Optimal preventive maintenance for equipment with two quality states and general failure time distributions". European Journal of Operational Research, vol. 180, no. 1, p. 329-353, 2007.
[16]  D. Pandey, M.S. Kulkarni, and P.Vrat, "A methodology for joint optimization for maintenance planning, process quality and production scheduling". Computers & Industrial Engineering, vol. 61, no. 4, p. 1098-1106, 2011.
[17]  R.Jamshidi, and M.M.SeyyedEsfahani, "Reliability-based maintenance and job scheduling for identical parallel machines". International Journal of Production Research(ahead-of-print), vol. 53, no. 4, p. 1216-1227.
[18]  M.M.Mazdeh, F. Zaerpour, A. Zareei, and A.Hajinezhad, "Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs". Applied Mathematical Modelling, vol. 34, no. 6, p. 1498-1510, 2010.
[19]  S. Browne, andU.Yechiali, "Scheduling deteriorating jobs on a single processor". Operations Research, vol. 38, no. 3, p. 495-498, 1990.
[20]  T.Ning, X. Duan, L. An, and T.Gou, “Research on Disruption Management of Urgent Arrival in Job Shop with Deteriorating Effect”. Journal of Intelligent & Fuzzy Systems, vol. 41, no. 1, p. 1247-1259, 2021.
[21]  S.Raut, S. Swami,andJ.N.Gupta, "Scheduling a capacitated single machine with time deteriorating job values". International Journal of Production Economics, vol. 114, no. 2, p. 769-780, 2008.
[22]  X.Huang, andM.Z. Wang, "Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties". Applied Mathematical Modelling, vol. 35, no. 3, p. 1349-1353, 2011.
[23]  T.Cheng, S.J. Yang, and D.L. Yang, "Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity". International Journal of Production Economics, vol. 135, no. 1, p. 154-161, 2012.
[24]  A.Berrichi, L. Amodeo, F. Yalaoui, E. Châtelet, and M.Mezghiche, "Bi-objective optimization algorithms for joint production and maintenance scheduling: application to the parallel machine problem". Journal of Intelligent Manufacturing, vol. 20, no. 4, p. 389-400, 2009.