Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions

Oliver Braun (), Fan Chung () and Ron Graham ()
Additional contact information
Oliver Braun: Trier University of Applied Sciences, Environmental Campus Birkenfeld
Fan Chung: University of California
Ron Graham: University of California

OR Spectrum: Quantitative Approaches in Management, 2016, vol. 38, issue 2, No 11, 540 pages

Abstract: Abstract We consider the following scheduling problem. We are given a set S of jobs which are to be scheduled sequentially on a single processor. Each job has an associated processing time which is required for its processing. Given a particular permutation of the jobs in S, the jobs are processed in that order with each job started as soon as possible, subject only to the following constraint: For a fixed integer $$B \ge 2$$ B ≥ 2 , no unit time interval $$[x, x+1)$$ [ x , x + 1 ) is allowed to intersect more than B jobs for any real x. There are several real world situations for which this restriction is natural. For example, suppose in addition to the jobs being executed sequentially on a single main processor, each job also requires the use of one of B identical subprocessors during its execution. Each time a job is completed, the subprocessor it was using requires one unit of time to reset itself. In this way, it is never possible for more than B jobs to be worked on during any unit interval. In Braun et al. (J Sched 17: 399–403, 2014a) it is shown that this problem is NP-hard when the value B is variable and a classical worst-case analysis of List Scheduling for this situation has been carried out. We prove a tighter bound for List Scheduling for $$B\ge 3$$ B ≥ 3 and we analyze the worst-case behavior of the makespan $$\tau _\mathrm{LPT}(S)$$ τ LPT ( S ) of LPT (longest processing time first) schedules (where we rearrange the set S of jobs into non-increasing order) in relation to the makespan $$\tau _o(S)$$ τ o ( S ) of optimal schedules. We show that LPT ordered jobs can be processed within a factor of $$2-2/B$$ 2 - 2 / B of the optimum (plus 1) and that this factor is best possible.

Keywords: Scheduling; Worst-case analysis; Time restrictions; LPT (longest processing time first) algorithm (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s00291-016-0431-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:orspec:v:38:y:2016:i:2:d:10.1007_s00291-016-0431-5

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-016-0431-5

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().