The Complexity Of Some Batching Scheduling And On-Line Scheduling Problems

Schedule is an important branch of combinatorial optimization. It is extensively applied in many fields, such as management science, computer science, production of industry and agriculture, transportation et al.. Batching scheduling and on-line scheduling are two important aspects of it, we mainly discuss them in this thesis.Four chapters are concluded in this thesis.In the first chapter, some notation, definitions and basic background information about the subject are introduced.In the second chapter, we consider an on-line scheduling of unit time jobs with rejection on identical parallel machines. In the standard three-field scheduling notation, the problem is denoted by Pm|on -line,Pj = 1| cj + ej. (Here, the rejection penalty ej, i.e. when job Jj arrivals, if we do not process it, we would be penalized at cost ej).In this chapter, we extend the case on one machine ([6]) to the case on arbitrary number identical parallel machines. We design an on-line algorithm G1 for the latter case, and give the competitive ratio 1/2(2 + ) 1.86602.In the third chapter, we mainly consider the application of copy method in batching scheduling. We firstly construct the contact between the batching scheduling and the classical scheduling.In this chapter, we mainly discuss the problems 1|rj,B| Cj and 1|rj, B|Lmax.After giving the definition of copy method, we present two impor-tant lemmata and discuss the NP-completeness of the above two minsum and minmax problems.In the fourth chapter, we discuss some problems of minimizing the total weighted completion time on single and parallel batch processing machines. We have known the NP-completeness of them in general ([17][18]). But none has ever discuss the special case of all jobs with identical processing time.In section 2 of the chapter, we present an optimal algorithm SFBLW for the problem 1|rj {0,r},B,pj =p|wjCj, and we get some conclusions.In the section 3, we also present an algorithm G for the problem Pm|B,pj = and prove the optimality of the algorithm.