An Algorithmic Study On Two Kinds Of New Scheduling Problems

As an important branch of combinatorial optimization, scheduling has been extensively applied to fields of production and manufacturing. Among varielty of existed models, scheduling with inventory constraints and that with severs are two original ones. The former is a scheduling model that arises from the veichle allocation and terminal management, while the latter has been found in network computing, textile industry and the courses of batch annealing process in steel industry. This thesis mainly studies the above scheduling problems, where the main issue will be formulating the mathematical models, designing algorithms and analyzing their performance. Five chapters are made.In Chapter1, we first introduce the basic concepts of scheduling, computational complexity and approximation algorithms,etc. Then a short review on the theory and algorithms of classical scheduling is made. Finaly, we give a detailed description of the models to be studied in reminder of the thesis.In the second chapter, we consider a single-machine scheduling problem subject to inventory constraints. This chapter mainly consists of two parts. The first part focuses on the problem with only one negative job, i.e.,1|inv|,n-|=1|∑wiCi. For this problem, both an NP-hardness proof and a greedy algorithm are provided. It is shown that though the greedy algorithm is unbounded in the sense of worst case, it performances fairly good in the average sense. In the second part, we pay our atention to the problem with arbitrary number of negative jobs, i.e.,1|inv,|n-|=n1|∑C1(n1≥1)n1∈Z+). We formulate our problem to a0-1integer programming model and present an algorithm namely Greedy-Merge to solve it. Computational results indicates that the Greedy-Merge algorithm performances good as well in the average sense.In Chapter3, we study the m parallel machines scheduling problem with a single server. There is a set of jobs to be processed on a set of m parallel and identical machines. Prior to processing on a machine, each job has to be loaded by a single server. Given equal lenth of jobs, we first prove that the SPT algorithm has a worst case ratio of2-1/m for the problem P,S1|si,pi=p|Cmax and the bound is tight. Then, we show that the algorithm also has a worst case ratio of3/2for the problem P, S1|s1,p1=p|∑CChapter4further discusses the single server scheduling problem of minimizing the total completion time on small number of machines. With careful analysis, we show that the worst case ratios of the SPT algorithm cannot exceed (?)2and (?)6-1for the two-machine case and three-machine case, respectively. Finally, some conclusion and remarks are made in Chapter5.