摘要
研究工件既可以在制造商机器上加工、又可以转包给承包商加工的m台机流水作业排序问题。考虑工件在制造商机器上以串行分批方式加工,即工件按串行方式接连在机器上成批加工,批加工时间为该批中所有工件的工时之和,且加工后被分批运送给客户;同时,因部分工件被转包给承包商加工,还考虑制造商需要支付一定的转包费用。在转包总费用不超过给定值情况下,研究极小化工件加工成本与运输成本之和的有效算法。其中,加工成本分别取制造商处工件最大完工时间及工件总完工时间,运输成本则与工件批数成正比。对于工件加工时间仅依赖于工件的情形,针对不同的加工成本,分析了问题的NP困难性及最优解的结构,分别设计了2个近似算法;对于工件加工时间仅依赖于机器的情形,则在分析解结构的基础上提出了2个多项式时间算法。
Flow shop scheduling where each job can be either processed in-house shop or outsourced to a subcontractor is studied.The jobs in-house are processed in serial batches,i.e.,the jobs are processed in batches on the machine in a serial manner and the processing time of a batch is the sum of the processing times of all jobs in the batch.And all the jobs are shipped to customers in batches after processing.Each of the outsourced jobs requires paying an outsourcing cost.The objective is to minimize the sum of the performance measure(the total completion time or the makespan)and transportation cost for in-house jobs,subject to a limit on total outsourcing cost.The transportation cost is proportional to the batch number of jobs.Two special cases where job’s processing time depends solely on job itself or on the machine are considered.In the first case,two approximation algorithms are designed respectively for different performance measures after the NP hardness of the problem and the structure of the optimal solution are analyzed.On the basis of analyzing the solution structure,two polynomial algorithms are proposed in the second case.
作者
陈荣军
唐国春
CHEN Rongjun;TANG Guochun(School of Sciences,Changzhou Institute of Technology,Changzhou Jiangsu 213032;School of Economics&Management,Shanghai Second Polytechnic University,Shanghai 201209,China)
出处
《重庆师范大学学报(自然科学版)》
北大核心
2025年第3期17-23,共7页
Journal of Chongqing Normal University:Natural Science
基金
国家自然科学基金面上项目(No.71371120)
教育部人文社会科学研究青年基金项目(No.23YJC790046)。
关键词
流水作业排序
转包
串行分批
近似算法
flow shop scheduling
outsourcing
serial batch
approximation algorithm
