基于最小最大遗憾的同型并行机鲁棒调度模型

研究了加工时间不确定的最小化总完工时间的同型并行机调度问题.在仅知加工时间所在区间的条件下,基于最小最大遗憾准则建立了同型并行机的鲁棒调度模型.估计出了最大遗憾值的情景(即最坏情景)发生在工件加工时间取区间上端点或下端点处,并指出任意调度的最大遗憾可以通过求解一个指派问题得到.证明了同型并行机鲁棒调度问题的最优解与经典的确定性问题的最优解在工件配置上相同.该问题可以转化为一个单机器鲁棒调度问题来处理.

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

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