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

【Abstract】 This paper studies an identical parallel machine scheduling problem of minimizing total completion time with uncertain processing times.The only information about the processing time of each job is that it can take any real value from a given interval.As such,a robust identical parallel machine scheduling model based on min-max regret criterion is developed.It is first pointed out that a regret-maximizing scenario(worst-case scenario) for any schedule belongs to a finite set of extreme point scenarios where the job processing times take on the upper bounds or the lower bounds of the intervals and the maximal regret for any schedule can be obtained by solving an assignment problem.Then it is proved that the jobs allocations in optimal robust schedule are identical to that in optimal schedule of deterministic scheduling problem.Based on the above results,the robust identical parallel machines scheduling problem can be solved by transferring it to a robust single machine scheduling problem.更多还原