Robust (min-max regret) single machine scheduling with interval processing times and total tardiness criterion
Robust (min-max regret) single machine scheduling with interval processing times and total tardiness criterion
复制标题
DOI：
10.1016/j.cie.2020.106838
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Shijin Wang;Wenli Cui;F. Chu;Jianbo Yu;J. Gupta
中科院分区：
文献类型：
--
作者：
Shijin Wang;Wenli Cui;F. Chu;Jianbo Yu;J. Gupta
研究了加工时间不确定的区间数据表示的鲁棒(最小-最大遗憾)单机调度问题。目标是在最坏情况下使总拖期与最优解的绝对偏差最小的稳健的作业序列。首先将问题描述为混合整数线性规划(MILP)模型，并假设中点情形下相应的确定性NP-Hard问题可以得到最优解，然后证明了中点情形下的最优调度是该问题的2-近似解。接下来，证明最坏的情况不一定在间隔处理时间的上限或下限。利用这些结果，提出了2-近似算法(2AA)、基于最坏情况的启发式算法(WSH)和基于近似最坏情况的启发式算法(AWH)，并对它们进行了实验评估，其中集成了评估解的最大遗憾的迭代过程。最后，对全文进行了总结，并对未来该领域的研究提出了一些有益的建议。
This paper studies a robust (min–max regret) single machine scheduling problem with uncertain processing times represented by interval data. The objective is to obtain robust sequences of jobs that minimize the absolute deviation of total tardiness from the optimal solution under the worst-case scenario. The problem is first formulated as a mixed-integer linear programming (MILP) model and assuming that the corresponding deterministic NP-hard problem for the mid-point scenario can be solved optimally, an optimal schedule under the mid-point scenario is then proved to be a 2-approximation solution to the problem. Next, the worst-case scenarios are proved to be not necessarily at the upper or lower limits of the interval processing times. Utilizing these results, a 2-approximation algorithm (2AA), a worst-case scenario-based heuristic (WSH), and an approximate worst-case-based heuristic (AWH) are proposed and empirically evaluated, in which an iterative procedure for evaluating the maximum regret of a solution is integrated. Finally, the paper is concluded by suggesting some fruitful directions for future research in this area.