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

Uniform-machine scheduling in shared manufacturing

考虑了共享制造环境下的同类机排序问题.在共享制造环境中,每个工件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.