Paper Info
Title
BRKGA-VNS for Parallel-Batching Scheduling on a Single Machine with Step-Deteriorating Jobs and Release Times.
Abstract
This paper investigates the problem of scheduling step-deteriorating jobs with release times on a single parallel-batching machine. The processing time of each job can be represented as a simple non-linear step function of its starting time. The machine can process up to c jobs simultaneously as a batch. The objective is to minimize the makespan, and we show that the problem is strongly NP-hard. Then, a hybrid meta-heuristic algorithm BRKGA-VNS combining biased random-key genetic algorithm (BRKGA) and variable neighborhood search (VNS) is proposed to solve this problem. A heuristic algorithm H is developed based on the structural properties of the problem, and it is applied in the decoding procedure of the proposed algorithm. A series of computational experiments are conducted and the results show that the proposed hybrid algorithm can yield better solutions compared with BRKGA, PSO (Particle Swarm Optismization), and VNS.
Year
DOI
Venue
2017
10.1007/978-3-319-72926-8_34
Lecture Notes in Computer Science
Keywords
DocType
Volume
Parallel-batching,Step-deteriorating,Release times,Makespan
Conference
10710
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Chunfeng Ma122.77
Min Kong2193.65
Jun Pei320226.56
P. M. Pardalos426945.19