Ćwik Michał, Józefczyk Jerzy
Faculty of Computer Science and Management, Wroclaw University of Science and Technology, Wybrzeze Wyspianskiego 27, 50-370 Wrocław, Poland.
Cent Eur J Oper Res. 2018;26(1):215-238. doi: 10.1007/s10100-017-0485-8. Epub 2017 Jul 29.
An uncertain version of the permutation flow-shop with unlimited buffers and the makespan as a criterion is considered. The investigated parametric uncertainty is represented by given interval-valued processing times. The maximum regret is used for the evaluation of uncertainty. Consequently, the minmax regret discrete optimization problem is solved. Due to its high complexity, two relaxations are applied to simplify the optimization procedure. First of all, a greedy procedure is used for calculating the criterion's value, as such calculation is NP-hard problem itself. Moreover, the lower bound is used instead of solving the internal deterministic flow-shop. The constructive heuristic algorithm is applied for the relaxed optimization problem. The algorithm is compared with previously elaborated other heuristic algorithms basing on the evolutionary and the middle interval approaches. The conducted computational experiments showed the advantage of the constructive heuristic algorithm with regards to both the criterion and the time of computations. The Wilcoxon paired-rank statistical test confirmed this conclusion.
考虑一种具有无限缓冲区且以完工时间为准则的排列流水车间的不确定版本。所研究的参数不确定性由给定的区间值加工时间表示。使用最大遗憾值来评估不确定性。因此，求解了极小极大遗憾离散优化问题。由于其高度复杂性，应用了两种松弛方法来简化优化过程。首先，使用贪心算法来计算准则值，因为这种计算本身就是一个NP难问题。此外，使用下界代替求解内部确定性流水车间。将构造性启发式算法应用于松弛优化问题。将该算法与先前基于进化和中间区间方法阐述的其他启发式算法进行了比较。进行的计算实验表明，构造性启发式算法在准则和计算时间方面都具有优势。威尔科克森配对秩统计检验证实了这一结论。
