New approximation algorithms for machine scheduling with rejection on single and parallel machine
- PDF / 410,266 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 70 Downloads / 209 Views
New approximation algorithms for machine scheduling with rejection on single and parallel machine Peihai Liu1
· Xiwen Lu1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper we consider three machine scheduling problems with the special feature that jobs may be rejected at a certain penalty. There are n jobs which are characterized by a release date, a processing time and a penalty. Each job is either accepted and then processed by one machine, or rejected and then a rejection penalty is paid. The objective is to minimize the maximum completion time of all accepted job plus the total penalties of all rejected jobs. When jobs have identical release dates, we present 1 )-approximation algorithm for the parallel machine problem. When jobs a ( 23 − 2m have general release dates, we propose a 43 -approximation algorithm for the single machine problem and a (1 + max{0.618, 1 − m1 })-approximation algorithm for the parallel machine problem, respectively. Keywords Scheduling · Rejection · Release date · Approximation algorithm · Worst-case ratio
1 Introduction In this paper, we consider three machine scheduling problems with rejection which was first introduced by Bartal et al. (2000). In such problems, the scheduler does not have to process all the jobs and thus a higher level decision of partitioning the set of jobs into a set of accepted and a set of rejected jobs has to be made prior to the scheduling decision. Then, the set of accepted jobs has to be efficiently scheduled on the machines so as to minimize a predefined scheduling criterion. One important application of scheduling with rejection arises in make-to-order production systems with
B
Peihai Liu [email protected] Xiwen Lu [email protected]
1
Department of Mathematics, East China University of Science and Technology, Shanghai 200237, People’s Republic of China
123
Journal of Combinatorial Optimization
limited production capacity and tight delivery requirements, where order rejection and scheduling decisions have to be made simultaneously (Cesaret et al. (2012)). Another important application of machine scheduling with rejection occurs in scheduling with an outsourcing option (Shabtay et al. (2013)). Since outsourcing can reduce and control operating costs, it has become a megatrend in many industries, most particularly in logistics and supply chain management. For example, Taiwan Semiconductor Manufacturing Company (TSMC) is the world’s largest semiconductor foundry. TSMC will manufacture chips for its customers, such as Apple Inc., HUAWEI, Qualcomm, Intel et al. When a new order come from its customer, TSMC will make decisions to give priority to the order, postpone the order, or reject the order. 1.1 Model description and notations The scheduling problems we study can be described formally as follows: We are given a single machine or a set of m identical parallel machines and a set of n jobs J = {J1 , J2 , . . . , Jn }. Associated with each job J j is a release date r j , a processing time p j and a rejectio
Data Loading...
