Near-linear-time approximation algorithms for scheduling a batch-processing machine with setups and job rejection
- PDF / 394,232 Bytes
- 14 Pages / 595.276 x 790.866 pts Page_size
- 101 Downloads / 223 Views
Near-linear-time approximation algorithms for scheduling a batch-processing machine with setups and job rejection Jinwen Ou1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper we study a single batch-processing machine scheduling model. In our model, a set of jobs having different release dates needs to be scheduled onto a single machine that can process a batch of jobs simultaneously at a time. Each batch incurs a fixed setup time and a fixed setup cost. The decision maker may reject some of the jobs by paying penalty cost so as to achieve a tight makespan, but the total rejection penalty cost is required to be no greater than a given value. Our model extends several existing batch-processing machine scheduling models in the literature. We present efficient approximation algorithms with near-linear-time complexities. Keywords Scheduling · Batch processing · Job rejection · Approximation algorithm · Performance analysis
1 Introduction 1.1 Model description There are given a set of n jobs J = {J1 , J2 , . . . , Jn } to be processed in batches by a single machine that can process a batch of jobs simultaneously. Each J j has a processing time p j , a release date r j and a rejection penalty w j . The number of jobs contained in a batch is unlimited. The jobs in the same batch have the same starting time and completion time. The processing time of a batch is defined as the longest processing time of the jobs contained in the batch. The starting time of a batch is required to be no less than the largest release date of the jobs contained in the batch. Before the processing of a job batch can start, a fixed setup time s and a fixed setup cost c are required. We assume that the machine is not allowed to process any job when a batch setup is prepared. Each J j is either accepted and then processed by the machine in some batch, or rejected and then a rejection penalty w j is paid. The total rejection penalty of the rejected jobs is required to be no greater than a given value R0 . The jobs in J will be partitioned into two disjoint subsets A and R, so that all
B 1
Jinwen Ou [email protected] Department of Management Administration, School of Management, Jinan University, Guangzhou 510632, People’s Republic of China
jobs in A are accepted, while all jobs in R are rejected, and the rejection constraint J j ∈R w j ≤ R0 is satisfied. The jobs in A will be further partitioned into y disjoint subsets B1 , . . . , B y , so that all jobs in Bi are processed as the i-th batch on the machine (i = 1, . . . , y), where y is a decision variable. Let Cˆ i denote the completion time of Bi on the machine for i = 1, . . . , y. The objective is to minimize the function z = α Cˆ y + (1 − α)(yc + J j ∈R w j ), i.e., the weighted sum of the makespan of the accepted jobs and the total cost (including the total batch setup cost and the total rejection penalty of the rejected jobs), where α ∈ (0, 1] is a given parameter that reflects the decision maker’s preference between the makespan and the
Data Loading...
