Online Serial-batch Scheduling And Off-line Mixed Batch Scheduling On A Single Machine

This dissertation studies the online serial-batch scheduling and the off-line mixed batch scheduling on a single machine. In the online serial-batch scheduling, a job's information is unknown until it is released. A batch processing machine can process several jobs in a serial batch at the same time. Each job has its set-up time, the processing time of a batch is equal to the total processing time of all jobs in it, and the setup time of a batch is given by the largest set-up time among the jobs in it. The objective is minimizing the makespan. Using the 3-field notation convention, the problem is denoted by l|s-batch. on-line, b=+∞,ri≤rj(?)si≥sj|Cmax.In the mixed batch scheduling, we have two families of jobs JA and JB, called A jobs and B jobs, respectively. The two families of jobs are processed on a common batch machine. But, A jobs and B jobs cannot be assigned into a common batch. Furthermore, the batches of A jobs are of parallel with capacity b(A), and the batches of B jobs are of serial with capacity b(B), set-up time s(B). Using the 3-field no-tation convention, the problem is denoted by l|s-p-batch. s(B), (b(A), b(B))|γ, whereγ∈{Cmax, Lmax,∑Cj,∑wjCj,fmax.The dissertation is organized as follows:In Chapter 1, we briefly introduced some definitions, notations and basic information about scheduling related to this paper.In Chapter 2, we study the online serial-batch scheduling. For problem l|s-batch, on-line, b=+∞,ri≤rj(?)si≥sj|Cmax we present a best possible flexible online algorithm of competitive ratio ((?)+1)/2.In Chapter 3, we study the two-family jobs serial-parallel mixed batch off-line schedul-ing on a single machine. The main results are as follows: .The scheduling problem l|s-p-batch,s(B),(∞,∞)Lmax can be solved in O(nAnBn) time..The scheduling problem l|s-p-batch,s(B),(∞,b(B))1∑Cj can be solved inO(nAnBn) time..The scheduling problem 1|s-p-batch,pj=1,s(B),b(A),b(B))|∑ujCj can be solved inO(nAnBn)time..The scheduling problem l|s-p-batch,s(B),(∞,b(B))|fmax can be solved in O(log(maxj fj(M))×(nlogM+nAnBn))time,where M is an upper bound of the completion times of the jobs.Finally,we summarize the dissertation and put forward some problems which we will consider further.