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

Hanane Krim (), Rachid Benmansour, David Duvivier, Daoud Aït-Kadi and Said Hanafi
Additional contact information
Hanane Krim: Polytechnic University of Hauts-de-France
Rachid Benmansour: Polytechnic University of Hauts-de-France
David Duvivier: Polytechnic University of Hauts-de-France
Daoud Aït-Kadi: University of Laval
Said Hanafi: Polytechnic University of Hauts-de-France

Computational Optimization and Applications, 2020, vol. 75, issue 1, No 11, 320 pages

Abstract: 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%.

Keywords: Single machine scheduling; Preventive maintenance; Mathematical model; Heuristic; Lower bounds (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-019-00142-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:75:y:2020:i:1:d:10.1007_s10589-019-00142-5

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-019-00142-5

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().