带有退化和资源约束的不同类型机排序问题

Unrelated parallel-machine scheduling problems with deterioration and resource-dependent processing time

讨论带有线性退化和线性资源约束的不同类型机排序问题。每个工件都有一个基本加工时间。工件的实际加工时间是与他的基本加工时间、开始加工时间、实际加工位置以及被分配的资源量相关的一般函数。分别讨论了2个排序问题,一个目标函数为每台机器的最大完工时间、总完工时间、加工时间绝对差以及资源分配之和;另一个目标函数为每台机器的最大完工时间、总等待时间、等待时间绝对差以及资源分配之和。目的是同时确定最优资源分配和工件最优的加工顺序,从而使每个目标函数极小化。通过将每个问题的目标函数转化为对应的指派问题,进而求解,并证明每个问题都是在多项式时间内可解的。

This paper considers unrelated parallel-machine scheduling problems with position dependent deteriorating jobs and resource allocation.actual processing time of a job is a function of its basic processing time,starting time,position and its resources allocation.In this paper,we focus on the two unrelated parallel machine problems that one objective function is the weighted sum of total load,total completion time,total absolute differences in completion time and total resource cost,and another function is the weighted sum of total load,total waiting time,total absolute differences in waiting times and total resource cost,respectively.The goal is to find the optimal sequence of jobs and the optimal resource allocation,separately. We first show that the problems can be transformed into corresponding assignment problems,and then proved that the problems can be solved in polynomial time under the proposed model.