Short Communication
Single-machine scheduling with waiting-time-dependent due dates

https://doi.org/10.1016/j.ejor.2007.08.015Get rights and content

Abstract

We consider a single-machine scheduling problem in which due dates are linear functions of the job waiting-times and the objective is to minimize the maximum lateness. An optimal sequence is constructed by implementing an index-based priority rule for a fixed value of the due date normalizing constant k. We determine in polynomial time all the k value ranges so that the optimal sequence remains the same within each range. The optimal due dates are computed as linear functions of the global optimal value of k. The overall procedure is illustrated in a numerical example.

Introduction

In many practical situations involving scheduling decisions the job due dates are assigned internally by the scheduler based on certain shop characteristics. Cheng and Gupta (1989) provide a comprehensive survey of scheduling research involving due date assignment decisions. One way of assigning job due dates is to take into account both job characteristics and the current shop status; e.g., the JIS method assigns due dates based on the number of jobs in the system (Weeks, 1979) and the JIQ method assigns due dates based on current queue lengths (Eilon and Chowdhury, 1976). The simulation results of Eilon and Chowdhury, 1976, Ragatz and Mabert, 1985 demonstrate the merits of these due date assignment methods.

The objective of this paper is to construct an optimal sequence and assign the optimal due dates analytically in a single-machine setting when due dates are linear functions of the job waiting-times and the objective is to minimize the maximum job lateness. To our knowledge, our results are the first analytical results for this type of problem. Specifically, we assume that in a non-preemptive single-machine setting all jobs from a given batch are available and ready for processing at the same time (e.g., at time zero). Let pj denote the processing time of job Jj and dj denote the baseline due date of Jj which is based exclusively on the characteristics of Jj. Then, the actual waiting-time-adjusted due date of Jj can be defined as dj=dj+kr=1j-1pr, where k is a normalizing constant and r=1j-1pr denotes the total processing time of all already processed jobs on the machine prior to Jj, since in our single-machine environment a job’s waiting-time is equal to the summation of the processing times of the already processed jobs. It is reasonable to assume that very long adjusted due dates will not be well-received by the customers and this can be prevented from happening by requiring that k  1. Our scheduling objective is to minimize the maximum job lateness (to be formally defined in the next section). We show that for a given value of the due date normalizing constant k, an optimal sequence can be constructed in O(n log n) time (where n is the number of jobs) by implementing an index-based priority scheduling rule. We also show how to compute (in polynomial time) the optimal value of k, k, when the cost of assigning due dates is taken into account. Our approach for computing k is complicated by the fact that as k varies, the corresponding optimal sequence varies as well.

Our model can be easily implemented in a dynamic environment since the derived optimal job sequencing rule is an index-based rule based only on job characteristics. Newly arriving jobs can be inserted in the proper place in the sequence of the still unprocessed jobs without any major difficulty. Consequently, our model can be used for setting due dates in many practical operations in which due dates are initially negotiated with the customers and then adjusted accordingly to actual shop conditions. Such operations include small printing shops, auto repair shops, etc. in which the initially negotiated due dates with the customers may be adjusted based on actual waiting-times.

Section snippets

The optimal sequence for a fixed k value

We formally introduce our problem for a fixed k value as follows: There are n jobs Jj, j = 1,  , n, (all available at time zero) to be scheduled non-preemptively on a continuously available single machine. Each job Jj has a processing time pj and a baseline due date dj. For any schedule (sequence) S of the n jobs, let J[j] denote the job in the jth position in S and let C[j] be the completion time of J[j] in S. The actual due date of J[j] in S, d[j], is a linear function of its waiting-time r=1j-1

Assignment of the optimal due dates

We now turn our attention to the problem of assigning the optimal due dates. In order to do so, we must determine the optimal k value for a given cost function.

Define the parametric maximum lateness for schedule S as Lmax(k) and observe that Lmax(k) is a non-increasing function of k since each d[j] is a non-decreasing function of k. This justifies the following total cost objective functionTC(k)=αk+Lmax(k),where α > 0 is a cost coefficient. The total cost in Eq. (3) is the sum of the cost of

Conclusions

We considered the problem of determining optimal due dates when due dates are linear functions of the job waiting-times in a single-machine setting under the Lmax objective. We showed that an optimal sequence can be determined in O(n log n) time by implementing an index-based priority rule for a fixed value of the due date normalizing constant k. We showed how to determine the global optimal k value in polynomial time which in turn led to the determination of the optimal due dates as linear

Acknowledgement

We would like to thank two anonymous referees for their constructive criticism which helped us improve an earlier version of the paper.

References (4)

There are more references available in the full text version of this article.
View full text