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.