Scheduling two groups of jobs with incomplete information

Guochuan Zhang; Xiaoqiang Cai; C. K. Wong

doi:10.1007/s11518-006-0121-y

Journal of Systems Science and Systems Engineering ›› 2003, Vol. 12 ›› Issue (1) : 73 -81. DOI: 10.1007/s11518-006-0121-y

Article

Scheduling two groups of jobs with incomplete information

Author information +

History +

PDF

Abstract

In real world situations, most scheduling problems occur neither as complete off-line nor as complete on-line models. Most likely, a problem arises as an on-line model with some partial information. In this article, we consider such a model. We study the scheduling problem P(n ₁,n ₂), where two groups of jobs are to be scheduled. The first job group is available beforehand. As soon as all jobs in the first group are assigned, the second job group appears. The objective is to minimize the longest job completion time (makespan). We show a lower bound of 3/2 even for very special cases. Best possible algorithms are presented for a number of cases. Furthermore, a heuristic is proposed for the general case. The main contribution of this paper is to discuss the impact of the quantity of available information in designing an on-line algorithm. It is interesting to note that the absence of even a little bit information may significantly affect the performance of an algorithm.

Keywords

Machine scheduling / worst-case analysis / on-line algorithm

Cite this article

Download citation ▾

Guochuan Zhang, Xiaoqiang Cai, C. K. Wong. Scheduling two groups of jobs with incomplete information. Journal of Systems Science and Systems Engineering, 2003, 12(1): 73-81 DOI:10.1007/s11518-006-0121-y

登录浏览全文

4963

注册一个新账户忘记密码

References

Publishing order | Descend order by publishing year | Descend order by cited within

[1]	Chen B., Van Vliet A., Woeginger G.J.. New lower and upper bounds for on-line scheduling. Operations Research Letters, 1994, 16: 221-230.

[2]	Chen, B., C.N. Potts and G.J. Woeginger, “A review of machine scheduling: Complexity, algorithms and approximability”, D.Z. Du and P. Pardalos, Handbook of Combinatorial Optimization, Kluwer Academic Publishers, 1998.

[3]	Faigle U., Kern W., Turan G.. On the performance of on-line algorithms for partition problems. Acta Cybernetica, 1989, 9: 107-119.

[4]	Graham R.L.. Bounds for certain multiprocessing anomalies. Bell System Technical J., 1966, 45: 1563-1581.

[5]	Graham R.L.. Bounds on multiprocessing timing anomalies. SIAM Journal of Applied Mathematics, 1969, 17: 416-429.

[6]	Gary M.R., Johnson D.S.. Strong NP-completeness results: motivation, examples and implications. Journal of ACM, 1978, 25: 499-508.

[7]	Gary M.R., Johnson D.S.. Computers and Intracability: A Guide to the Theory of NP-Completeness, 1979, San Francisco: Freeman

[8]	Lee C.Y.. Parallel machines scheduling with nonsimultaneous machine available time. Discrete Applied Mathematics, 1991, 30: 53-61.

[9]	Sgall, J., “On-line scheduling”, In A. Fiat and G, J. Woeginger, Online Algorithms — The state of the art, Lecture Notes in Computer science, Vol. 1442, pp196–231, 1998.