共享制造环境下的同类机排序问题  

Uniform-machine scheduling in shared manufacturing

作　　者：宋嘉欣 孔凡雨 霍雨佳 苗翠霞[1] 赵韵杰 SONG Jiaxin;KONG Fanyu;HUO Yujia;MIAO Cuixia;ZHAO Yunjie(School of Mathematical Sciences,Qufu Normal University,273165,Qufu,Shandong,PRC)

机构地区：[1]曲阜师范大学数学科学学院,山东省曲阜市273165

出　　处：《曲阜师范大学学报（自然科学版）》2023年第4期15-23,共9页Journal of Qufu Normal University(Natural Science)

基　　金：国家自然科学基金(12271295,12001313);山东省自然科学基金(ZR2022MA019);山东省大学生创新创业训练计划项目(S202210446018)。

摘　　要：考虑了共享制造环境下的同类机排序问题.在共享制造环境中,每个工件Jj都有一个可以加工的机器集Mj,Jj可以被分别给Mj的某一台机器加工,也可以一定服务成本分配给其他剩余机器进行加工.该文的目标是最小化工件的最大完工时间加总服务成本.对于机器台数是固定常数情况,该文对经典加工模型和简单退化加工模型分别提出了基于程序划分的全多项式时间近似方案.对总服务成本不超过给定上界的限制下最小化最大完工时间问题,给出了其整数规划模型.In this paper,the uniform-machine scheduling with shared manufacturing is considered,in which each job J j has a restricted set M j of machines on which it can be processed,the job not only can be processed on one machine of M j,but also can be processed on one of the remaining machines with a certain cost.The objective is to minimize the makespan plus the total service cost.When the number of machines is fixed,fully polynomial time approximation scheme based on the procedure partition for the classical and simple deterioration processing time are proposed,respectively.Furthermore,the integer linear programming model is given,for minimizing the makespan under the constraints that the total service cost is no more than a given upper bound.

关 键 词：排序 共享制造 同类机 全多项式时间近似方案 

分 类 号：O224[理学—运筹学与控制论]