Parallel-batching scheduling of deteriorating jobs with non-identical sizes and rejection on a single machine
- PDF / 1,141,258 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 42 Downloads / 189 Views
Parallel-batching scheduling of deteriorating jobs with non-identical sizes and rejection on a single machine Min Kong1,3 · Xinbao Liu1,3 · Jun Pei1,2,3 · Zhiping Zhou1,2 · Panos M. Pardalos2 Received: 6 January 2018 / Accepted: 7 January 2019 © Springer-Verlag GmbH Germany, part of Springer Nature 2019
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 of thecomplexity the dynamic help nto reduce n w j to O n 2 i1 w j . For the genprogramming algorithm from O n! n 2 i1 eral 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. Keywords Parallel-batching scheduling · Deteriorating jobs · Job rejection · Setup time · Dynamic programming algorithm · Non-identical sizes
B B
Min Kong [email protected] Jun Pei [email protected]
1
School of Management, Hefei University of Technology, Hefei 230009, People’s Republic of China
2
Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA
3
Key Laboratory of Process Optimization and Intelligent Decision-Making of Ministry of Education, Hefei 230009, People’s Republic of China
123
M. Kong et al.
1 Introduction In the last decade, there has been significant interest in scheduling problems that involve batching, where multiple jobs with non-identical sizes can be processed by a batching machine simultaneously and the total size of the jobs in a batch cannot exceed the capacity of the machine [1–5]. In practice, parallel-batching scheduling problems are encountered in many environments such as semiconductor manufacturing, composite manufacturing, parallel computing [6–11]. Nevertheless, most literature on batching scheduling problem with non-identical sizes assumed that the job rejection was not allowed, which did not conform manufacturing practices. Actually, job processing manufacturers would process some selected orders in priority considering cost and resource constraints. The rejected orders may, for example, be outsourced for processing at a certain cost. Such machine scheduling problem with rejection was first introduced by Bartal et al. [12] when solving a parallel mach
Data Loading...
