An on-line algorithm for the bounded p-batch scheduling with chain precedence constraints and unit processing time

• Autorzy: Nong Q. , Yuan J.
• Języki publikacji: EN

Abstrakty

EN

We consider the problem of scheduling unit time jobs with release dates on a single machine which can process up to b jobs simultaneously as a batch under on-line setting. There are chain precedence constraints on the jobs. The release dates and the precedence relations of the jobs remain unknown until their arrivals. The scheduling problem involves assigning all the jobs to batches and determining the starting times of the batches in such a way that the maximum completion time of the jobs (makespan) is minimized. In this paper we present an on-line algorithm with a worst-case ratio of radic3 for the problem.

Słowa kluczowe

EN

scheduling; on-line; batch; makespan

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2006
• Tom: Vol. 31, No. 3-4
• Strony: 277--290
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Nong Q.

autor

Yuan J.

• Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People's Republic of China,

Bibliografia

• [1] Dror M., Kukiak W., and Dell'Olrno P., Strong-weak chain constrained scheduling. Kicerca Operativa, 27, 1998, 35-49.
• [2] Cheng T.C.E., Ng C.T., Yuan J.J. and Liu Z.H., Single machine parallel batch scheduling subject to precedence constraints, Naval Research Logistics, 51, 2004, 949-958.
• [3] Chen B., Deng X.T. and Zang W.A., On-line scheduling a batch processing system to minimize total weighted job completion time. Journal of Combinatorial Optimization, 8, 2004, 85-95.
• [4] Deng X.T.. Poon C.K. and Zhang Y.Z.. Approximation algorithms in batch processing. Lecture notes in Computer Science. 1741. 2000, 153-162.
• [5] Lee C.Y. and Uzsoy R.. Minimizing makespan on a single batch processing machine with dynamic job arrivals. Lit J Prod Res, 37, 1999, 219-236.
• [6] Lee C.Y., Urizoy R.. and Martin-Vega L.A., Efficient algirithms for scheduling semiconductor burn-in operations. Operation Research, 40, 1992, 764-775.
• [7] Liu Z.H., Yuan J.J. and Cheng T.C.E.. On scheduling an unbounded batch machine, Operation Research Letters, 31. 2003, 42-48.
• [8] Poon C.K. and Yu W.C., On-line scheduling algorithms for a batch machine with finite capacity, Journal of Combinatorial Optimization. 9. 2005. 167-186.
• [9] Zhang G.C., Cai X.Q. and Wong C.K.. On-line algorithms for minimizing makespan on batch processing machines, Naval Research Logistics. 48, 2001. 241-258.
• [10] Zhang G.C., Cai X.Q. and Wong C.K., Optimal on-line algorithms for scheduling on parallel batch processing machines, ILE Transactions, 35, 2003. 175-181.