Random Demand Batch Under The Restriction Of Resource Scheduling Model And Algorithm

Due to the large number of applications in the manufacturing, the schedulingproblem has been paid more and more attention from the20thcentury. It’s committed tomake a reasonable allocation with the limited resource in a certain time, which isexpected to finish the different tasks as efficiently as possible. It is a making decisionprocess, the goal of which is to optimize one or more objective functions. The stochasticbatch scheduling, which is also known as the online batch scheduling, is one of themore rapid develop model in modern scheduling field. The stochastic means that theinformation of the jobs is unknown before they arrive to the system, for example, thearrival time, arrival number, due date, weight and whether there are any new job arrives.Compared to the traditional single scheduling, the batch scheduling puts the job to forma batch to process. Because it can improve the production efficiency and conserveresource, the batch scheduling has been paid increasing attention from the scholars ofoperation research, management science, engineering and other fields.To most machine environment and the object functions, the stochastic batchscheduling model is an NP-hard problem. So it becomes a powerful tool that using theproximity of the online algorithm and the offline algorithm to measure the performanceof the algorithm, which is based on the competitive ratio of approximate thinking. Andthis approach has been recognized by most scholars. It usually refers to the proximity ofthe objective function and the offline algorithm in the worst case. And it is the infimumof the ratio value. In this thesis, we use some relevant rules of heuristic algorithms todeal with the batch scheduling model, which the information is unknown before the jobsarrive to the system. Finally, we show that the algorithm has competitiveness by thecompetitive ratio and data simulation. In this thesis we consider the parallel machineenvironment and the online batch scheduling model with the jobs randomly arrived. Thespecific works are as follows:（1） We introduce some different scheduling models, some related knowledge ofcompetitive ratio, the main study methods of batch scheduling model and the researchstatus of related model. （2） Because the target function is the minimize total weight completed time and theminimize total weight delay, we put forward the algorithm competitive ratio which isless than1+α to parallel machine with limited batch processing capacity. Hereα=β_m can be obtained through（1+β_m）^m+1=β_m+2, m is the number of machines.（3） At last, we study the parallel machines with m=2, and the model having twodifferent family jobs. Now the objective function is the minimize of the maximumcompletion time. We obtain the algorithm with the competitive ratio smaller than1.（4） We simulate the case with the job random arrival by using the Poisson process,and then verify the specific algorithm by simulation data.