On-line Batch Scheduling With Delivery Time

Scheduling is an important research field of combinatorial optimization. It is widely used in scientific management, computer science, industrial and agricultural production, transportion and other sectors. Batch scheduling and on-line scheduling are two new kinds of modern scheduling models. They both have very important applying meanings. While the on-line batch scheduling problems with delivery time is an important manifestation of the application in supply-chain theory. This article is about the study for this problem.There are three chapters in this paper.In the first chapter, some notations, definitions and basic background information about the scheduling theory are introduced. We mainly introduce the computational complexity theory, batch scheduling,on-line scheduling and the main results and innovations of this paper.In the second chapter,we mainly analyze the on-line algorithms of two modles with delivery time and batch processing. They are independent delivery model and batch delivery modle with batch processing. We prove that the competitive ratio of two special problems in independent delivery model both are 1+δ, whereδ=((?)-1)/2 .We present a semi on-line theory for the independent delivery model for the first time, and also we firstly present a new delivery model, that is batch delivery model.In the end we analyze the competitive ratio of the same algorithm for the two models.In the third chapter we conside the proportioned scheduling problems BPP in batching unifom parral machines for the first time. This problem is also NP-complete when the objective function is C_max. We give two approximate algorithms: QBFF and QM ,and prove that their competitive ratios are not morethan B/a+1, 3/2+ρrespectively,where a = min{a_j} andρ= (m -1)S₁ /(?)S₁.