Single-machine group technology scheduling with resource allocation and slack due window assignment including minmax criterion
研究了单机环境下成组技术调度中，通过资源分配缩短加工时间，并基于松弛到期窗口最小化最大窗口成本与总资源成本之和的问题，提出了多项式时间算法和启发式算法。
The minmax problem for scheduling of group technology with slack due to window assignment under single-machine is investigated. That is, jobs are divided into the same group for continuous processing with similar production characteristics, and resources are allocated to each job to reduce the processing time based on the slack due window of each group, which can be expressed in the form of linear (including compression rate) and convex (including lower bounds on the processing time) functions of the resources, with the objective of minimizing the sum of the maximum slack due window cost (including earliness/tardiness, common flow allowance, and window size) and total resource allocation. Firstly, it is verified that the minimized maximum window cost is polynomial-time solvable for constant processing time. Next, polynomial-time solution algorithms for the target cost are proposed for the special case where the function coefficients are group-position-dependent. Third, for the general case where the coefficients are group-position-independent, an NEH-based heuristic algorithm is proposed, under the consideration of the processing times associated with the two resources, which are used as the upper bound for the branch-and-bound algorithm. Finally, a computational study of the random data is conducted to verify the effectiveness of the proposed algorithms.