Chain-reentrant shop with an exact time lag: new results
研究了两台机器链式重入车间调度问题，其中第一台机器上的两个操作之间需满足精确时间滞后，目标是最小化完工时间。针对相同滞后情形，提出了启发式算法并给出实验结果，同时证明了新的NP难结果和若干多项式可解情形。
The two-machine chain-reentrant shop scheduling with the objective of minimizing the makespan, assumes that the tasks pass from the first machine to the second and return back to the first machine. In this paper, we consider the same problem in which an exact time lag between the two operations on the first machine is imposed. In Amrouche and Boudhar (2016) the authors proved that this problem is NP-hard in the strong sense in the case of identical time lags . We propose heuristic algorithms with empirical results for the latter. In addition, we establish a new NP-hardness result and some polynomial cases.