Single-Machine and Parallel-Machine Parallel-Batching Scheduling Considering Deteriorating Jobs, Various Group, and Time-Dependent Setup Time

This paper studies a set of novel integrated scheduling problems by taking into account the combinatorial features of various groups, parallel-batching, deteriorating jobs, and time-dependent setup time simultaneously under the settings of both single-machine and parallel-machine, and the objective of the studied problems is to minimize the makespan. In order to solve the single-machine scheduling problem, we first investigate the structural properties on jobs sequencing, jobs hatching, and batches sequencing for the optimal solution, and then develop a scheduling rule. Moreover, for solving the parallel-machine scheduling problem, we exploit the optimal structural properties and hatching rule, and propose a novel hybrid AIS-VNS algorithm incorporating Artificial Immune System algorithm (AIS) and Variable Neighbourhood Search (VNS). Extensive computational experiments are conducted to evaluate the performance of the proposed AIS-VNS algorithm, and comparison results show that the proposed algorithm performs quite well in terms of both efficiency and solution quality.