运筹与管理2025，Vol.34Issue(9)：39-45,7.DOI:10.12005/orms.2025.0273
工件可拒绝的真空热处理炉调度优化
Scheduling of Vacuum Heat Treatment Furnaces with Job Rejection
摘要
Abstract
A vacuum heat treatment furnace is an innovative and environmentally friendly heat treatment technology that combines heat treatment with vacuum technology.It is widely used in the manufacturing proces-ses of high-end metal components such as molds,fasteners,and precision coupling parts.It is primarily applied in industries such as automotive,high-speed railways,nuclear power,aerospace,and aviation.In comparison to other processes,vacuum heat treatment has a longer processing time.After vacuum treatment process,the metal components exhibit high quality and extended lifespan.Due to high purchased cost and restricted installation space,the number of vacuum heat treatment furnaces is limited,and the furnace is the bottleneck machine in real production.When facing production anomalies such as machine failures or urgent rush orders,a common approach is to use rescheduling methods to quickly restore production.However,if the production anomalies exceed a certain critical threshold,rescheduling strategies may be ineffective.By borrowing the concept of"sacrificing a knight to get the king",it becomes necessary to reject a portion of jobs to ensure the on-time delivery of the accepted ones. The scheduling of vacuum heat treatment furnace is modeled as mixed batch model.Multiple jobs can be processed on the mixed batch machine simultaneously.When the number of jobs processed in a mixed batch is arbitrary,we call this model as unbounded.The processing time of a mixed batch is the weighted sum of the maximum processing time in the batch and the sum of the processing times for all the job in the same batch.The mixed batch model combines the parallel batch model and serial batch model,which increase the complexity of the mixed batch scheduling problem.In addition,different job release times usually lead to the reduction of utili-zation of furnaces,and thus it is necessary to reject some jobs.To enhance the utilization of vacuum heat treat-ment furnaces,the rejection of jobs with low cost-effectiveness is considered.This paper studies unbounded mixed batch scheduling with release dates and rejection,where jobs are either accepted for processing or rejected by paying rejection cost.The makespan and total rejection cost are considered as the objectives in this paper. Rejecting jobs usually reduce the makespan of furnaces and increase the total rejection cost,and thus it is important to decide the rejected jobs and schedule the accepted jobs.In order to balance the makespan and the total rejection cost,this paper studies three models:the linear weighted model,the constrained model and the Pareto optimization model.The first model is a linear weighted model where objective function is a linear combi-nation of the makespan and the total rejection cost.Based on whether the job is accepted or rejected and its contribution to the objective function,four scenarios have been considered for discussion.A dynamic program-ming algorithm is designed,and the time complexity of the algorithm is analyzed.The second model is the constrained model,where the total rejection cost or the makespan does not exceed a certain threshold value,and the other objective function is minimized.A dynamic programming algorithm is proposed and its time complexity is analyzed.The third model is Pareto optimization model.The iterative process involves repeatedly constraining the total rejection cost to a certain threshold value and then optimizing the makespan.Based on the analysis of the four scenarios,a dynamic programming algorithm is yielded.After iteration times,the Pareto frontier can be obtained.Lastly,the time complexity of the algorithm is presented. The insights derived from unbounded mixed batch scheduling with release dates and rejection are as follows.When jobs concentrate on their arrivals during specific time periods,it is possible to achieve line balancing by rejecting certain jobs strategically to optimize the workload on various lines.Jobs with specific arrival times result in more constraints when grouping them for processing.Changes in orders or urgent insertions can reduce the flexibility of scheduling.Rejecting some jobs strategically can alleviate production bottlenecks and enhance the overall flexibility of the scheduling scheme.Taking the advantage over the production flexibility arising from job rejection,a more accurate and scientific schedule can be devised for customers with jobs having different arrival times.This allows for the implementation of differentiated custom services,ultimately enhancing customer satisfaction.These insights highlight the importance of adaptability and strategic decision-making in the face of dynamic production scenarios,emphasizing the potential benefits of rejecting certain jobs to optimize overall system performance and meet customer expectations more effectively.关键词
混合批处理调度/拒绝成本/动态规划算法/时间复杂度Key words
mixed batch scheduling/rejection cost/dynamic algorithm/time complexity分类
管理科学引用本文复制引用
胥军,冯鸽,赵义,王艳,胡国锋,范国强..工件可拒绝的真空热处理炉调度优化[J].运筹与管理,2025,34(9):39-45,7.基金项目
国家自然科学基金青年科学基金项目(C类)(72502179) （C类）
陕西省自然科学基础研究计划项目(2024JC-YBQN-0574) （2024JC-YBQN-0574）
国家自然科学基金青年科学基金项目(52105529) （52105529）
中央高校基本科研业务费专项资金项目(XJSJ23095) （XJSJ23095）
