带有退化效应和不可用区间的并行批排序问题

在制造业中,处理机由于长时间使用而发生故障或进行维护、保养等原因,产生一些不可用区间;并且工件的实际加工时间往往与它的开始加工时间有关。研究一种带有退化效应和不可用区间的无界单机并行批处理机排序问题。在这一模型中,工件的实际加工时间是其开始加工时间的线性递增函数。而并行批处理机中,同批工件同时开始加工,同时完工,且批一旦开始加工就不可中断;每批的加工时间等于这批工件中加工时间的最大者;同批中工件的完工时间都相同,为这批的完工时间。讨论的目标函数为最大完工时间问题。通过对最优解性质的分析,给出了求解此问题的多项式时间的最优算法。

Parallel-batch scheduling problem with forbidden intervals and deteriorating effect

In manufacture industry, the processing machine has some forbidden intervals which are occupied by machine breakdowns or maintenance durations in which the machine is not available. Moreover, the actual processing time is related to its starting time. This paper considers an unbounded parallel-batch scheduling problem with linear deteriorating effect and forbidden intervals. In this model, the jobs with deteriorating effect, i. e. , each job＇s processing time is an increasing simple linear function of its starting time. In the parallel-batch scheduling, all jobs in the same batch start processing and finish simultaneously and once processing started of a batch, it cannot be interrupted. The processing time of a batch is given by the largest processing time of the jobs in the batch, the completion time of all jobs in a hatch is equal to the completion time of the batch. In this paper, the objective function is maximum makespan, we analyzed properties of the optimal solution, provided a polynomial time optimal algorithm.