Skip to Main content Skip to Navigation
Journal articles

Heuristics for the single machine weighted sum of completion times scheduling problem with periodic maintenance

Abstract : 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%.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03517880
Contributor : Julie Cagniard Connect in order to contact the contributor
Submitted on : Saturday, January 8, 2022 - 12:23:01 PM
Last modification on : Sunday, January 9, 2022 - 3:29:28 AM

Identifiers

Collections

Citation

Hanane Krim, Rachid Benmansour, David Duvivier, Daoud Aït-Kadi, Said Hanafi. Heuristics for the single machine weighted sum of completion times scheduling problem with periodic maintenance. Computational Optimization and Applications, Springer Verlag, 2020, 75 (1), pp.291-320. ⟨10.1007/s10589-019-00142-5⟩. ⟨hal-03517880⟩

Share

Metrics

Les métriques sont temporairement indisponibles