Certain Batch Scheduling Problem With Transportation Time

We consider a single batch machine on-line scheduling problem with delivery time. Foreach job Jj, its arrival time, processing time and delivery time are denoted by r_j, p_j andq_j, respectively. For a given batch machine, it can process several jobs simultaneously asa batch, all jobs in a common batch machine have the same starting time and completiontime, a running batch cannot be preempted. The processing time of a batch is equal to thelongest processing time of the jobs in the batch. Once the processing of a job is completed itis delivered to the destination, the objective is to minimize the time by which all jobs havebeen delivered. This thesis mainly study two models: one is online batch scheduling withdelivery times related to processing times and the other is an unbounded parallel machinescheduling problem with delivery times of two families of jobs. The thesis is split up intofour chapters, we first introduce some preliminary concepts related to scheduling problemsand outline the background and the related study about batch scheduling all around theworld.In chapter 2, we study a single batch machine on-line scheduling problem with deliverytimes. For each job Jj, p_j≥βq_j(β≥0.4472), we provide an on-line algorithm with com-petitive ratio√52+ 1, and the result is the best possible; For each job Jj, q_j =βp_j(β≥0),we provide an on-line algorithm with competitive ratio√β2+2β+5?β+12 , and a lower bound ofthe problem isβ+5β+1+12 .In chapter 3, we consider an unbounded parallel machine scheduling problem with de-livery times of two families of jobs. The jobs from di?erent families can not be processedsimultaneously in the same batch machine. We provide an on-line algorithm with competi-tive ratio 2 for the problem. When all jobs are available simultaneously, we give a forwarddynamic programming algorithm. When the jobs have agreeable processing and deliverytime, i.e. for any two jobs Ji and Jj, p_i≥p_j implies q_i≥q_j, we provide an on-line algorithmwith competitive ratio√147 +3for this problem, and the result is the best possible. In chapter4, we give the future study and research.