Abstract
We study a variant of classical scheduling, which is called scheduling with “end of sequence” information. It is known in advance that the last job has the longest processing time. Moreover, the last job is marked, and thus it is known for every new job whether it is the final job of the sequence. We explore this model on two uniformly related machines, that is, two machines with possibly different speeds. Two objectives are considered, maximizing the minimum completion time and minimizing the maximum completion time (makespan). Let s be the speed ratio between the two machines, we consider the competitive ratios which are possible to achieve for the two problems as functions of s. We present algorithms for different values of s and lower bounds on the competitive ratio. The proposed algorithms are best possible for a wide range of values of s. For the overall competitive ratio, we show tight bounds of ϕ + 1 ≈ 2.618 for the first problem, and upper and lower bounds of 1.5 and 1.46557 for the second problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Angelelli E, Nagy A, Speranza M, Tuza Z (2004) The on-line multiprocessor scheduling problem with known sum of the tasks. J Sched 7:421–428
Azar Y, Regev O (2001) Online bin stretching. Theor Comput Sci 268:17–41
Dósa G, He Y (2004) Semi-Online algorithms for parallel machine scheduling problems. Computing 72:355–363
Epstein L (2003) Bin Stretching revisted. Acta Inform 39(2):97–117
Epstein L (2005) Tight bounds for bandwidth allocation on two links. Discrete Appl Math 148(2):181–188
Epstein L, Favrholdt LM (2005) Optimal non-preemptive semi-online scheduling on two related machines. J Algorithms 57(1):49–73
Epstein L, Noga J, Seiden SS, Sgall J, Woeginger GJ (2001) Randomized online scheduling on two uniform machines. J Sched 4(2):71–92
Graham R (1966) Bounds for certain multiprocessing anomalies. Bell Sys Techn J 45:1563–1581.
Graham R (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17(2):416–429
He Y, Zhang G (1999) Semi on-line scheduling on two identical machines. Computing 62:179–187
Kellerer H, Kotov V, Speranza MG, Tuza Z (1997) Semi on-line algorithms for the partition problem. Oper Rese Lett 21:235–242
Sanders P, Sivadasan N, Skutella M (2004) Online Scheduling with Bounded Migration. In: Proceedings of automata, languages and programming: 31st international colloquium, (ICALP 2004), lecture notes in computer science. Vol 3142, pp 1111–1122.
Seiden S, Sgall J, Woeginger G (2000) Semi-online scheduling with decreasing job sizes. Oper Res Lett 27:215–221
Sgall J (1998) On-line scheduling. Online algorithms—the state of art, lecture notes in computer science. vol 1442, pp 196–231
Tan Z, He Y (2002) Semi-on-line problems on two identical machines with combined partial information. Oper Res Lett 30:408–414
Zhang G (1997) A simple semi on-line algorithm for P2//C max with a buffer. Inform Process Lett 61:145–148.
Zhang G, Ye D (2002) A note on on-line scheduling with partial information. Comput Math Appl 44:539–543.
Author information
Authors and Affiliations
Corresponding author
Additional information
D. Ye: Research was supported in part by NSFC (10601048).
Rights and permissions
About this article
Cite this article
Epstein, L., Ye, D. Semi-online scheduling with “end of sequence” information. J Comb Optim 14, 45–61 (2007). https://doi.org/10.1007/s10878-006-9040-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-006-9040-6