考虑模具约束和开机成本的并行机调度问题研究

Parallel Machine Scheduling Problem Considering Mold Constraints and Machine Opening Cost

受企业实际的注塑排产问题启发,本文研究了一类考虑模具约束和开机成本的相同并行机调度问题,目标是最小化加权延迟成本、换模成本和开机成本之和。构建了混合整数规划模型,证明了问题必定存在无机器空闲的最优解,提出了新的工作分配规则以确保产生的解都无机器空闲。在此基础上,设计了修改的ATCS算法(ATCS-MOD)和基于列表调度的遗传算法(GA-LS)两种算法。大规模数值实验证明GA-LS求解效果优于CPLEX和ATCS-MOD,更显著优于传统ATCS算法,同时也证明了新工作分配规则相比传统ATCS规则的优越性。

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.