Affiliations: [1] School of Management, Hefei University of Technology, Hefei, China | [2] Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, USA. E-mail: feiyijun.ufl@gmail.com | [3] Key Laboratory of Process Optimization and Intelligent Decision-Making of Ministry, of Education, Hefei, China
Correspondence:
[*]
Corresponding author.
Abstract: 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 batching, 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 batching 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.
Keywords: scheduling, parallel-batching, group scheduling, deterioration, time-dependent setup time
Journal: Informatica, vol. 29, no. 2, pp. 281-301, 2018
