New results for scheduling to minimize tardiness on one machine with rejection and related problems
- PDF / 353,416 Bytes
- 8 Pages / 595.276 x 790.866 pts Page_size
- 38 Downloads / 195 Views
New results for scheduling to minimize tardiness on one machine with rejection and related problems Christos Koulamas1
· George Steiner2
Accepted: 23 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We study the total weighted tardiness problem with rejection on a single machine. We present new recursive algorithms and approximation results for the agreeably weighted case and a variety of related problems with and without deadlines. Keywords Production/scheduling: sequencing · Deterministic · Single machine
1 Introduction According to Congram et al. (2002) minimizing the sum of weighted tardiness on a single machine is an “NP-hard archetypal machine scheduling problem” whose exact solution appears very difficult even on very small inputs. In this paper we study this problem with the added provision that not all jobs need to be scheduled; instead, some may be rejected with a certain penalty. In highly loaded production systems, accepting all orders (jobs) may cause substantial delays in the completion of some orders which may result in high tardiness costs. In such situations, it may be beneficial for the firm to reject the processing of some orders by either out-sourcing them (at an additional cost) or rejecting them altogether. Thus scheduling with rejection allows the integration of scheduling and sales decisions in a single model. This led to increased interest by researchers to study various scheduling models with rejection. For more detail, we refer to the survey paper on scheduling with rejection by Shabtay et al. (2013). Throughout the paper we will use the three-field notation of Graham et al. (1979), with the denominations and convenDedicated to the memory of Dr. Rui Zhang.
B
Christos Koulamas [email protected] George Steiner [email protected]
1
Department of Information Systems and Business Analytics, College of Business Florida International University, Miami, FL, USA
2
Operations Management Area, McMaster University, Hamilton, ON, Canada
tions of the paper by Shabtay et al.(2013). Thus our general problem will be denoted by 1|rej| j∈S w j T j + j∈J \S e j , where J = {1, 2, . . . , n} denotes the set of all jobs, S ⊆ J is the set of scheduled jobs, p j is the processing time of job j ∈ J , d j is its due date, d j is its deadline (if any), C j denotes its completion time, T j = max{C j − d j , 0} is its tardiness, w j is its tardiness penalty per unit of time and e j is the penalty to be paid if the job is rejected. We also assume that all data are integers. There are also many situations in supply chain scheduling when the supplier finds it impossible to meet the promised due dates for some orders. Steiner and Zhang (2011) present a model for the rescheduling of orders with simultaneous assignment of attainable revised due dates to minimize due date escalation and tardiness penalties for the supplier. They call it the Revised delivery-time quotation with tardiness penalties problem and show that it is equivalent to minimizing the total tardines
Data Loading...
