Research On Flow-shop Scheduling With Job Rejection And Intermediate Transportation

Scheduling is one of the most important branches of operational research. Up to now,a large amount of scheduling models under various machine environments, restrictions and objective functions have been studied. In this thesis, we consider scheduling problems on a two flow-shop machines with integrated production and transportation. In order to save time or cost, the coordination between job production and job transportation in the scheduling with job rejection has been widely discussed in the literature. There are usually two traditional kinds to transport all jobs. The first kind always sends the semi-finished jobs to another machine for further process. The second transports the finished jobs to their customers or the warehouse. In this paper, we adopt the first kind of transportation.In addition, the transportation of jobs is in connection with the limits of transporters,including the number limits and capacity limits. The structure and the main results of this thesis are as follows:· In Chapter 1, we introduce the background of the problems, some scheduling terms,and some basic results and algorithms.· In Chapter 2, we study the scheduling problem TF2 | rej,v ? n | Cmax +?ej in which there is a sufficient number of transporters between the two stages. For this n problem, we present a dynamic programming algorithm with running time O(n (?)(p2j +t) max{p1j+t})? a 2-approximation algorithm, and an FPTAS.· In Chapter 3, we study the scheduling problem TF2 | rej,sj =1 | Cmax +? ej in which all the jobs have the same size. For this problem, we present a heuristic algorithm with the worst case performance ratio of 2.· In Chapter 4, we study the scheduling problem TF2 | rej,sj | Cmax +?ej in which the jobs have different sizes. For this problem, we present a heuristic algorithm with the worst case performance ratio of 11/5.· In Chapter 5, we study the scheduling problem TF2 | rej, p1j =p1,v, Sj | Cmax+?? ej in which all the jobs have a common processing time in the first machine and the number of the transporter is fixed. For this problem, we present a dynamic programming algorithm with running time O(cv+2vv+3n2v+1p1(?)p2j).