×

Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions. (English) Zbl 1339.90128

Summary: 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 \geq 2\), no unit time interval \([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 [O. Braun et al., J. Sched. 17, No. 4, 399–403 (2014; Zbl 1305.68041)] 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\geq 3\) and we analyze the worst-case behavior of the makespan \(\tau_{\mathrm{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)\) of optimal schedules. We show that LPT ordered jobs can be processed within a factor of \(2-2/B\) of the optimum (plus \(1\)) and that this factor is best possible.

MSC:

90B35 Deterministic scheduling theory in operations research

Citations:

Zbl 1305.68041
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Braun O, Chung F, Graham RL (2014a) Single processor scheduling with time restrictions. J Sched 17:399-403 · Zbl 1305.68041 · doi:10.1007/s10951-013-0342-0
[2] Braun O, Chung F, Graham RL (2014b) Bounds on single processor scheduling with time restrictions. In: Fliedner T, Kolisch R, Naber A (eds) Proceedings of the 14th International Conference on Project Management and Scheduling, pp 48-51 · Zbl 1305.68041
[3] Garey MR, Johnson DS (1979) Computers and Intractability: a guide to the theory of np-completeness W.H. Freeman, New York · Zbl 0411.68039
[4] Graham RL (1966) Bounds for certain multiprocessing anomalies. Bell Syst Tech J 45:1563-1581 · Zbl 0168.40703 · doi:10.1002/j.1538-7305.1966.tb01709.x
[5] Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17:416-429 · Zbl 0188.23101 · doi:10.1137/0117039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.