A combinatorial evolutionary algorithm for unrelated parallel machine scheduling problem with sequence and machine-dependent setup times, limited worker resources and learning effect

摘要

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.