Minmax scheduling problems with common flow-allowance

Abstract

In due-date assignment problems with a common flow-allowance, the due-date of a given job is defined as the sum of its processing time and a job-independent constant. We study flow-allowance on a single machine, with an objective function of a minmax type. The total cost of a given job consists of its earliness/tardiness and its flow-allowance cost components. Thus, we seek the job schedule and flow-allowance value that minimize the largest cost among all the jobs. Three extensions are considered: the case of general position-dependent processing times, the model containing an explicit cost for the due-dates, and the setting of due-windows. Properties of optimal schedules are fully analysed in all cases, and all the problems are shown to have polynomial time solutions.

Appendix

Proofs of Lemmas 1–3 (Property 8)

Consider an optimal schedule S ₁ in which (l) and (k) are the indices of two consecutive jobs, such that P _(l)>P _(k). Assume that job (l) starts at time t. We create a new schedule S ₂ by replacing jobs (l) and (k).

Lemma 1:

• An optimal schedule exists in which the early jobs are scheduled according to SPT.

Proof:

• Assume that jobs (l) and (k) in S ₁ are early, thus their costs (in S ₁) are:

  
  

  The costs of jobs (k) and (l) in sequence S ₂ are:

  

  Since P _(l)>P _(k) and α>0:

  

  Thus, schedule S ₁ is not optimal (and the early jobs must be scheduled according to SPT). □

Lemma 2:

• An optimal schedule exists in which the tardy jobs are scheduled according to SPT.

Proof:

• Assume that jobs l and k are tardy, and thus their costs in the sequence S ₁ are:

  
  

  The costs of jobs (k) and (l) in S ₂ are:

  

  Again, since P _(l)>P _(k) and β⩾γ>0:

  

  implying that schedule S ₁ is not optimal (and the tardy jobs must be scheduled according to SPT as well). □

Lemma 3:

• An optimal schedule exists in which the processing time of the last early job is not larger than that of the first tardy job.

Proof:

• In the sequence S ₁, let (l) be the last early job (which starts at time t), and the following job (k) is the first tardy job. The costs of these jobs in S ₁ are:

  
  

  As before, we assume P _(l)>P _(k), and schedule S ₂ is obtained by replacing jobs (k) and (l). There are three sub-cases regarding the status of jobs (k) and (l) in the sequence S ₂:

  Sub-case 1::

  In S ₂ job (k) is early and job (l) is tardy:

  

  

  It is easily verified (since P _(l)>P _(k) and β⩾γ>0) that (A.3)<(A.1) and (A.4)⩽(A.2).

  Sub-case 2::

  In S ₂ both jobs (k) and (l) are early:

  

  

  Here, (A.5)<(A.1) and (A.6)<(A.1).

  Sub-case 3::

  In S ₂ both jobs (k) and (l) are tardy:

  

  

  In this case (A.7)<(A.2) and (A.8)⩽(A.2).

  In all three sub-cases, S ₁ is shown to be non-optimal, implying that an optimal schedule exists in which the processing time of the last early job is never larger than that of the first tardy job. □