Paper Info
Title
Parallel-batching scheduling of deteriorating jobs with non-identical sizes and rejection on a single machine
Abstract
This paper studies the bounded parallel-batching scheduling problem considering job rejection, deteriorating jobs, setup time, and non-identical job sizes. Each job will be either rejected with a certain penalty cost, or accepted and further processed in batches on a single machine. There is a setup time before processing each batch, and the objective is to minimize the sum of the makespan and the total penalty. Several useful preliminaries for arranging accepted job with identical size are proposed. Based on these preliminaries, we first investigate a special case where all the jobs are considered to have the identical size, and develop a dynamic programming algorithm to solve it. The preliminaries help to reduce the complexity of the dynamic programming algorithm from $$ O\left( {n!n^{2} \sum\nolimits_{i = 1}^{n} {w_{j} } } \right) $$ to $$ O\left( {n^{2} \sum\nolimits_{i = 1}^{n} {w_{j} } } \right) $$. For the general problem with non-identical job sizes, we propose a hybrid algorithm combining heuristic with dynamic programming algorithm (H-DP) to obtain satisfactory solutions within reasonable time. Finally, the effectiveness and efficiency of the H-DP algorithm are illustrated by a series of computational experiments.
Year
DOI
Venue
2020
10.1007/s11590-019-01389-x
Optimization Letters
Keywords
DocType
Volume
Parallel-batching scheduling, Deteriorating jobs, Job rejection, Setup time, Dynamic programming algorithm, Non-identical sizes
Journal
14
Issue
ISSN
Citations 
4
1862-4472
1
PageRank 
References 
Authors
0.36
17
6
Name
Order
Citations
PageRank
Min Kong1193.65
Xin-Bao Liu225426.14
Jun Pei320226.56
Jun Pei451.10
Zhiping Zhou510.69
P. M. Pardalos626945.19