Parallel machine scheduling with completion-time-based criteria and sequence-dependent deterioration. (March 2019)

• Record Type: Journal Article
• Authors: Ding, Junwen; Shen, Liji; Lü, Zhipeng; Peng, Bo
• Is Part Of: Computers & operations research. Volume 103(2019)
• Page Start: 35
• Page End: 45
• Publication Date: 2019-03
• Subjects: Parallel machine scheduling -- Deteriorating effects -- Ejection chain; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.10.016
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: An ejection chain algorithm (ECA)is proposed for the considered problem. Some important properties are developed. ECA improves the previous best known results for 388 large instances. Abstract: This paper presents an ejection chain algorithm (ECA) for parallel machine scheduling problems with sequence dependent deteriorating effects to minimize completion-time-based criteria. We first derive some important properties which are consistent when minimizing makespan and total weighted completion time, and help to guide algorithm design. The proposed ECA adopts the ejection chain mechanism to create powerful moves. Several distinctive features are incorporated into ECA to enhance its effectiveness and efficiency. Applied to benchmark problem instances, ECA obtains all optimal solutions with a hit ratio of 100% for small problem instances. Moreover, it improves the previous best known results for 388 large instances, and consumes less computational time.