A combinatorial evolutionary algorithm for unrelated parallel machine scheduling problem with sequence and machine-dependent setup times, limited worker resources and learning effect. (1st August 2021)

• Record Type: Journal Article
• Authors: Zhang, Like; Deng, Qianwang; Lin, Ruihang; Gong, Guiliang; Han, Wenwu
• Is Part Of: Expert systems with applications. Volume 175(2021)
• Publication Date: 2021-08-01
• Subjects: Unrelated parallel machine scheduling -- Sequence and machine-dependent setup times -- Workers resources -- Learning effect; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2021.114843
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A new model of NUPMSP considering worker resources and learning effect is proposed. A combinatorial evolutionary algorithm is presented to solve the model. The makespan and total energy consumption are optimized simultaneously. Three effective methods are proposed to obtain high-quality initial solutions. Abstract: The existing papers on unrelated parallel machine scheduling problem with sequence and machine-dependent setup times (UPMSP-SMDST) ignore the worker resources and learning effect. Given the influence and potential of human factors and learning effect in real production systems to improve production efficiency and decrease production cost, we propose a UPMSP-SMDST with limited worker resources and learning effect (NUPMSP). In the NUPMSP, the workers have learning ability and are categorized to different skill levels, i.e., a worker's skill level for a machine is changing with his accumulating operation times on the same machine. A combinatorial evolutionary algorithm (CEA) which integrates a list scheduling ( LS ) heuristic, the shortest setup time first ( SST ) rule and an earliest completion time first ( ECT ) rule is presented to solve the NUPMSP. In the experimental phase, 72 benchmark instances of NUPMSP are constructed to test the performance of the CEA and facilitate future study. The Taguchi method is used to obtain the best combination of key parameters of the CEA. The effectiveness of the LS, SST and ECT is verified based on 15 benchmark instances. Extensive experiments conducted to compare the CEA with some well-known algorithms confirm that the proposed CEA is superior to these algorithms in terms of solving accuracy and efficiency.