不确定加工时间下同型并行机的鲁棒排程

在现实作业排程中,工件加工时间常常是不确定的。考虑到同型并行机的现实和理论意义,本文研究了加工时间不确定情况下以工期(最大完工时间)为目标的同型并行机排程问题。为了确定最优鲁棒排程,采用最小最大遗憾准则。其中,加工时间没有给出概率信息,而是用区间表示。经证明,该问题是一个NP-难问题且求解困难。为简化问题便于求解,本文给出了最大遗憾的计算公式,还证明出最坏情景出现在端点值,即各工件加工时间不是取区间上界就是下界。然后,提出了一种可以求出该问题最优解的迭代松弛算法并分析了其计算量。最后总结了本文的主要研究工作以及未来的研究方向。

Robust Scheduling for Identical Parallel Machines with Uncertain Processing Times

In practice,schedulers often confront with uncertain processing times for jobs.Considering the theoretical and practical importance of identical parallel machine scheduling,we study the identical parallel machine scheduling problem with the makespan(maximum complete time) criterion and uncertain processing times in this paper.In order to determine the optimal robust schedule,we adopt the min-max regret criterion.The processing times are specified as intervals without probability information.We prove this problem is NP-hard and difficult to solve.The function to calculate the maximal regret is proposed and the worst-case scenario exists where the processing times are extreme point of their intervals,either the upper bounds or the lower bounds.Both can simplify the problem and be helpful to find the optimal solution.Then we give an exact algorithm,iterative relaxation procedure,to seek the optimal solution and analyze its complexity.Finally,we summarize the main work of this paper and the future research.