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

Parallel Machine Scheduling Problem Considering Mold Constraints and Machine Opening Cost

作　　者：李金霖[1,2] 尹成龙 LI Jinlin;YIN Chenglong(School of Business,Central South University,Changsha 410083,China;Urban Smart Governance Laboratory of Hunan Province,Changsha 410083,China)

机构地区：[1]中南大学商学院,湖南长沙410083 [2]湖南省城市智慧治理实验室,湖南长沙410083

出　　处：《运筹与管理》2024年第4期105-111,共7页Operations Research and Management Science

基　　金：教育部人文社会科学基金项目(20YJC630062);国家自然科学基金资助项目(71501194)。

摘　　要：受企业实际的注塑排产问题启发,本文研究了一类考虑模具约束和开机成本的相同并行机调度问题,目标是最小化加权延迟成本、换模成本和开机成本之和。构建了混合整数规划模型,证明了问题必定存在无机器空闲的最优解,提出了新的工作分配规则以确保产生的解都无机器空闲。在此基础上,设计了修改的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 heurist

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

分 类 号：C935[经济管理—管理学] O223[理学—运筹学与控制论]