Heuristics for the single machine weighted sum of completion times scheduling problem with periodic maintenance. (English) Zbl 1432.90060
Summary: This paper tackles the single machine scheduling problem with periodic preventive maintenance in order to minimize the weighted sum of completion times. This criterion is certainly less studied than the makespan but it remains nonetheless interesting on the theoretical and practical levels. Indeed, the weights can quantify the holding cost per unit of time of the products to transform. Thus, this criterion can represent the global holding cost. This problem is proved to be NP-hard and a mixed integer linear programming formulation is proposed to solve small size instances of the problem. To solve large instances, we proposed three properties for this problem which generalize already existing works. These properties have been of great use in designing efficient heuristics capable of solving instances with up to 1000 jobs. To evaluate the performances of the proposed heuristics, lower bounds based on special cases of the problem are provided. Computational experiments show that the average percentage error of the best heuristic is less than 10%.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90B25 | Reliability, availability, maintenance, inspection in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
single machine scheduling; preventive maintenance; mathematical model; heuristic; lower boundsReferences:
| [1] | Ángel-Bello, F.; Álvarez, A.; Pacheco, J.; Martínez, I., A single machine scheduling problem with availability constraints and sequence-dependent setup costs, Appl. Math. Model., 35, 4, 2041-2050 (2011) · Zbl 1217.90101 |
| [2] | Ben-Daya, M.; Ait-Kadi, D.; Duffuaa, So; Knezevic, J.; Raouf, A., Handbook of Maintenance Management and Engineering (2009), Berlin: Springer, Berlin |
| [3] | Benmansour, R.; Allaoui, H.; Artiba, A.; Hanafi, S., Minimizing the weighted sum of maximum earliness and maximum tardiness costs on a single machine with periodic preventive maintenance, Comput. Oper. Res., 47, 106-113 (2014) · Zbl 1348.90243 |
| [4] | Benmansour, R.; Allaoui, H.; Artiba, A.; Iassinovski, S.; Pellerin, R., Simulation-based approach to joint production and preventive maintenance scheduling on a failure-prone machine, J. Qual. Maint. Eng., 17, 3, 254-267 (2011) |
| [5] | Benmansour, R., Artiba, A., Duvivier, D., Ramat, E., Ait-Kadi, D.: Scheduling of production and maintenance activities under reliability constraint. In: 9th International Conference on Modeling, Optimization & Simulation (2012) |
| [6] | Chen, W., Minimizing total flow time in the single-machine scheduling problem with periodic maintenance, J. Oper. Res. Soc., 57, 4, 410-415 (2006) · Zbl 1086.90020 |
| [7] | Chen, Wj, An efficient algorithm for scheduling jobs on a machine with periodic maintenance, Int. J. Adv. Manuf. Technol., 34, 11-12, 1173-1182 (2007) |
| [8] | Chen, Y.; Zhang, A.; Tan, Zy, Single machine scheduling with semi-resumable machine availability constraints, Appl. Math. J. Chin. Univ., 26, 2, 177-186 (2011) · Zbl 1240.90140 |
| [9] | Ebrahimy Zade, A.; Fakhrzad, Mb, A dynamic genetic algorithm for solving a single machine scheduling problem with periodic maintenance, ISRN Ind. Eng., 2013, 11 (2013) |
| [10] | Garey, Mr; Johnson, Ds, Computers and Intractability; A Guide to the Theory of NP-Completeness (1979), San Francisco: W.H. Freeman and Company, San Francisco · Zbl 0411.68039 |
| [11] | Graham, Rl; Lawler, El; Lenstra, Jk; Kan, Ar, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044 |
| [12] | He, J.; Li, Q.; Xu, D., Scheduling two parallel machines with machine-dependent availabilities, Comput. Oper. Res., 72, 31-42 (2016) · Zbl 1349.90352 |
| [13] | Ji, M.; He, Y.; Cheng, Te, Single-machine scheduling with periodic maintenance to minimize makespan, Comput. Oper. Res., 34, 6, 1764-1770 (2007) · Zbl 1159.90404 |
| [14] | Kacem, I.; Chu, C., Minimizing the weighted flow time on a single machine with the resumable availability constraint: worst case of the WSPT heuristic, Int. J. Comput. Integr. Manuf., 21, 4, 388-395 (2008) |
| [15] | Kacem, I.; Chu, C., Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period, Eur. J. Oper. Res., 187, 3, 1080-1089 (2008) · Zbl 1137.90494 |
| [16] | Kacem, I.; Chu, C.; Souissi, A., Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times, Comput. Oper. Res., 35, 3, 827-844 (2008) · Zbl 1278.90161 |
| [17] | Kacem, I.; Paschos, Vt, Weighted completion time minimization on a single-machine with a fixed non-availability interval: differential approximability, Discrete Optim., 10, 1, 61-68 (2013) · Zbl 1258.90040 |
| [18] | Kantorovich, L., The mathematical method of production planning and organization, Manag. Sci., 6, 4, 363-422 (1939) |
| [19] | Lee, Cy, Machine scheduling with an availability constraint, J. Global Optim., 9, 3-4, 395-416 (1996) · Zbl 0870.90071 |
| [20] | Lee, Cy; Liman, Sd, Single machine flow-time scheduling with scheduled maintenance, Acta Inform., 29, 4, 375-382 (1992) · Zbl 0738.68043 |
| [21] | Lee, Jy; Kim, Yd, Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance, Comput. Oper. Res., 39, 9, 2196-2205 (2012) · Zbl 1251.90162 |
| [22] | Li, G.; Liu, M.; Sethi, Sp; Xu, D., Parallel-machine scheduling with machine-dependent maintenance periodic recycles, Int. J. Prod. Econ., 186, 1-7 (2017) |
| [23] | Liao, C.; Chen, W., Single-machine scheduling with periodic maintenance and nonresumable jobs, Comput. Oper. Res., 30, 9, 1335-1347 (2003) · Zbl 1037.90031 |
| [24] | Low, C.; Hsu, Cj; Su, Ct, A modified particle swarm optimization algorithm for a single-machine scheduling problem with periodic maintenance, Expert Syst. Appl., 37, 9, 6429-6434 (2010) |
| [25] | Ma, Y.; Chu, C.; Zuo, C., A survey of scheduling with deterministic machine availability constraints, Comput. Ind. Eng., 58, 2, 199-211 (2010) |
| [26] | Nesello, V.; Subramanian, A.; Battarra, M.; Laporte, G., Exact solution of the single-machine scheduling problem with periodic maintenances and sequence-dependent setup times, Eur. J. Oper. Res., 266, 498-507 (2017) · Zbl 1403.90354 |
| [27] | Qi, X.; Chen, T.; Tu, F., Scheduling the maintenance on a single machine, J. Oper. Res. Soc., 50, 1071-1078 (1999) · Zbl 1054.90550 |
| [28] | Roux, O.; Duvivier, D.; Quesnel, G.; Ramat, E., Optimization of preventive maintenance through a combined maintenance-production simulation model, Int. J. Prod. Econ., 143, 1, 3-12 (2013) |
| [29] | Sadfi, C., Kacem, I., Liu, W.: Lower bounds for total weighted completion scheduling problem with availability constraints. In: Computers & Industrial Engineering, CIE 2009, pp. 159-163. IEEE (2009) |
| [30] | Sadfi, C., Penz, B., Rapine, C.: A dynamic programming algorithm for the single machine total completion time scheduling problem with availability constraints. In: Eighth International Workshop on Project Management and Scheduling, Valence, Spain (2002) · Zbl 1065.90041 |
| [31] | Sadfi, C.; Penz, B.; Rapine, C.; Błażewicz, J.; Formanowicz, P., An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints, Eur. J. Oper. Res., 161, 1, 3-10 (2005) · Zbl 1065.90041 |
| [32] | Smith, We, Various optimizers for single-stage production, Nav. Res. Logist. Q., 3, 1-2, 59-66 (1956) |
| [33] | Wang, G.; Sun, H.; Chu, C., Preemptive scheduling with availability constraints to minimize total weighted completion times, Ann. Oper. Res., 133, 1-4, 183-192 (2005) · Zbl 1119.90023 |
| [34] | Xu, D.; Yang, Dl, Makespan minimization for two parallel machines scheduling with a periodic availability constraint: mathematical programming model, average-case analysis, and anomalies, Appl. Math. Model., 37, 14, 7561-7567 (2013) · Zbl 1426.90145 |
| [35] | Yang, Sl; Ma, Y.; Xu, Dl; Yang, Jb, Minimizing total completion time on a single machine with a flexible maintenance activity, Comput. Oper. Res., 38, 4, 755-770 (2011) · Zbl 1202.90148 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
