AN ON-LINE ALGORITHM FOR THE BOUNDED P-BATCH SCHEDULING WITH CHAIN PRECEDENCE CONSTRAINTS AND UNIT PROCESSING TIME

摘要

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 3~(1/2) for the problem.