Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints

Gwo Ji Sheen, Lu Wen Liao

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

In this paper we consider the problem of scheduling n preemptive jobs on m machines with identical speed under machine availability and eligibility constraints when minimizing maximum lateness (Lmax). The lateness of a job is defined to be its completion time minus its due date, and Lmax is the maximum value of lateness among all jobs. We assume that each machine is not continuously available at all time throughout the planning horizon and each job is only allowed to be processed on specific machines. Network flow technique is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time two-phase binary search algorithm to verify the feasibility of the problem and to solve the scheduling problem optimally if a feasible schedule exists. Finally, we show that the time complexity of the algorithm is O ((n + (2 n + 2 x))3 log (UB - LB)). Most literature in parallel machine scheduling assume that all machines are continuously available for processing and all jobs can be processed at any available machine throughout the planning horizon. But both assumptions might not be true in some practical environment, such as machine preventive maintenance and machines that have different capabilities to process jobs. This type of scheduling problem is seldom studied in the literature. The purpose of this paper is to examine the scheduling problem with machines with identical speed under machine availability and eligibility constraints. The objective is to minimize maximum lateness. We formulate this scheduling problem into a series of maximum flow problems with different values of Lmax. A polynomial time two-phase binary search algorithm is proposed to verify the feasibility of the problem and to determine the optimal Lmax.

Original languageEnglish
Pages (from-to)2266-2278
Number of pages13
JournalComputers and Operations Research
Volume34
Issue number8
DOIs
StatePublished - Aug 2007

Keywords

  • Availability constraint
  • Binary search
  • Eligibility constraint
  • Lateness
  • Machines with identical speed
  • Network flows
  • Scheduling

Fingerprint

Dive into the research topics of 'Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints'. Together they form a unique fingerprint.

Cite this