Parallel machine scheduling with completion-time-based criteria and sequence-dependent deterioration

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.