关键词: 并行机调度, 模具约束, 开机成本, 遗传算法

Abstract: This study is driven by an industrial case concerning the scheduling of plastic injection machines in a switch factory. The injection workshop produces plastic parts for about 300 types of switches, and every two weeks it needs to deliver thousands of batches of parts to the assembly workshop, where a part may be delivered in multiple batches. Each batch of a part is treated as an indivisible job, characterized by a due date and mold requirements. Whenever two consecutive jobs involve different types of parts, a mold change is necessary, incurring setup time and cost. The decision-maker must determine the optimal number of operational machines, the job assignment and job sequence for each machine, considering the mold constraints and setup time/cost. The objective is to minimize the total cost, i.e., the sum of weighted tardiness cost, setup cost, and machine opening cost. Comparable scheduling problems are prevalent in small and medium-sized manufacturing enterprises in China, yet this particular problem has not been addressed in existing literature.
The problem is formulated as a mixed integer linear programming. It is proven that an optimal solution always exists without any machine idle time, meaning that a machine will never be idle unless all the jobs assigned to it have been completed. To ensure the absence of machine idle time, a new dispatching rule is proposed. The underlying principle is very similar to the ATCS (Apparent Tardiness Cost with Setups)dispatching rule introduced by CHEN and WU (2006): whenever a machine is available, we evaluate the priority index of all unassigned jobs, and select the job with the highest priority for assignment. The process continues until all jobs are assigned. However, our rule differs from the ATCS rule in that the selected job should be assigned to the machine where it can be completed the earliest, rather than to the machine just available. The distinction becomes significant when every part is delivered in many batches and the number of molds for a part is very limited. Based on this rule, a heuristic (named the ATCS-MOD heuristic) and a genetic algorithm incorporating a list scheduling heuristic (named the GA-LS algorithm) are designed to solve the problem. The GA-LS algorithm includes scheduling generated by the ATCS-MOD rule for various numbers of operational machines in its initial population, while the ATCS-MOD heuristic simply selects the best scheduling as the solution. The computational experiments conducted on a dataset comprising 640 randomly generated instances validate the effectiveness of the proposed dispatch rule and algorithms.
The performance of the proposed algorithms is firstly compared with the CPLEX solver in 160 small-sized instances. The CPLEX solver finds optimal solutions to 51 instances, while providing feasible solutions to the remaining instances, with an average runtime of 498 seconds. In contrast, the GA-LS algorithm achieves comparable or slightly superior solutions to the CPLEX solver in less than 1 second. On average, the GA-LS solution is 0.15% better than the CPLEX solution. In some instances, the GA-LS solution is worse than the CPLEX solution, but the cost increase never exceeds 2.49%. The computational results in 480 large-sized instances further reinforce the effectiveness of the proposed algorithms. The CPLEX solver fails to find any feasible solutions in most large-sized instances within 600 seconds, whereas the ATCS-MOD heuristic and the GA-LS algorithm require less than 0.01 and 36 seconds, respectively, to solve an instance.
Both the ATCS-MOD heuristic and GA-LS algorithm outperform the traditional ATCS heuristic in literature. By simply replacing the traditional ATCS rule with our dispatching rule, the ATCS-MOD heuristic gets an average of 22.23% cost reduction over the traditional ATCS heuristic. This result clearly proves the superiority of our dispatching rule. The GA-LS algorithm consistently outperforms both heuristics in all instances, achieving solutions with an average cost that is 31.56% lower than that of the traditional ATCS heuristic.

Key words: parallel machine scheduling, mold constraint, machine opening cost, genetic algorithm