On-line Scheduling On Partial Batch-machine

With regard to scheduling problem of two identical parallel machines, most of theliteratures either consider that two parallel batch processing machines can handle up toseveral jobs simultaneously,(.i.e.,B=∞) or consider that two normal machines can handleup to only one job(.i.e.,B= 1) between parallel batch scheduling and classical scheduling.In this paper, we consider that parallel batch processing machine is the first machine M₁,but the second machine is normal machine M₂.In chapter 2, on-line scheduling problem investigated here can be described as follows.There are two identical parallel machines; all information of jobs (release date and processing time) is unknown before the beginning of scheduling, but released one by one alongwith the flowing of time. The goal is to minimize the makespan. By using the generalnotation for scheduling problem introduced by Graham et al. [21], this problem is denotedby P2|on-line,p-batch, B₁=∞, B₂ = 1|C_max.We show that the considered problem has no on-line algorithm with competitive ratioless than 1+α. We also provide online algorithm with competitive ratio 2 for the problem.In chapter 3, we mainly consider that on-line scheduling problem can be describedas follows. There are two identical parallel machines;the jobs are equal-proccessing-time,and along with their chains-precedence constraints, are released at different times. Thegoal is to minimize the makespan. By using the general notation for scheduling problem introduced by Graham et al. [21], this problem is denoted by P2|on-line,p-batch, chainst,P_j=p, B₁=∞, B₂=1|C_max.We show that the considered problem has no on-line algorithm with competitive ratioless than 1 +α, we also give a best possible algorithm of this problem.