Paper Info
Title
Scheduling jobs on a single serial-batching machine with dynamic job arrivals and multiple job types
Abstract
This paper investigates a scheduling model with certain co-existing features of serial-batching, dynamic job arrival, multi-types of job, and setup time. In this proposed model, the jobs of all types are first partitioned into serial batches, which are then processed on a single serial-batching machine with an independent constant setup time for each new batch. In order to solve this scheduling problem, we divide it into two phases based on job arrival times, and we also derive and prove certain constructive properties for these two phases. Relying on these properties, we develop a two-phase hybrid algorithm (TPHA). In addition, a valid lower bound of the problem is also derived. This is used to validate the quality of the proposed algorithm. Computational experiments, both with small- and large-scale problems, are performed in order to evaluate the performance of TPHA. The computational results indicate that TPHA outperforms seven other heuristic algorithms. For all test problems of different job sizes, the average gap percentage between the makespan, obtained using TPHA, and the lower bound does not exceed 5.41 %.
Year
DOI
Venue
2016
10.1007/s10472-015-9449-7
Annals of Mathematics and Artificial Intelligence
Keywords
Field
DocType
Serial-batching scheduling,Dynamic job arrival,Multiple job types,Single machine,Setup time,90B35
Hybrid algorithm,Computer science,Scheduling (computing),Upper and lower bounds,Constructive,Real-time computing,Artificial intelligence,Job queue,Mathematical optimization,Heuristic,Job shop scheduling,Job scheduler,Machine learning
Journal
Volume
Issue
ISSN
76
1
1012-2443
Citations 
PageRank 
References 
1
0.36
10
Authors
6
Name
Order
Citations
PageRank
Jun Pei120226.56
Xin-Bao Liu225426.14
Wenjuan Fan314110.09
P. M. Pardalos426945.19
Athanasios Migdalas533027.26
Shanlin Yang678760.80