Algorithm Research For Some Flowshop Scheduling Problems

In this thesis we study the lower bounds and algorithms of some on-line and semi-online flowshop scheduling problems and single machine problems. We first consider the on-line and semi-line flowshop scheduling problems with the objective of minimizing the makespan. Jobs arrive over time or over a list. Then we consider single machine and flowshop problems with availability constraints.The paper consists of six parts. In Chapter one, we first introduce basic concepts of combinatorial optimization and scheduling problems. Then we give a review of on-line and semi-online scheduling. At last, we introduce the flowshop problems with availability constraints.In Chapter two, a preemptive on-line flowshop scheduling problem is considered. The objective is to minimize the makespan. Jobs arrive independently over time, i.e., the information of a job is not know until its arrival. We first give a lower bound of 1.137 for the problem, and provide an on-line algorithm. Then we prove that the algorithm is 3/2-competitive for the special case of the problem with only two arrival times.In Chapter three, we consider semi-online flowshop scheduling problems on non-preemptive and preemptive versions respectively. We study their semi-online versions with partial information of job size on two machines, such as the maximum (minimum) processing time or total processing time on one of the machines. We give lower bounds of all the problems above respectively. Then we provide an on-line algorithm with com-petitive ratio of 3/2 for non-preemptive and preemptive semi-online problems with optimal value known in advance. For preemptive semi-online problem with known total process-ing time on first machine, we also give an on-line algorithm with competitive ratio of 3/2.In Chapter four, we mainly study two machine flowshop problem with availability constraints. A resumable scenario is assumed, i.e., if a job cannot be finished before the interval it is continued after the machine becomes available again. The objective is to minimize the makespan. It is known that no algorithm for the problem with several availability constraints on the second machine has a constant competitive ratio. For an approximate case of the problem with several availability constraints on both machines, we show an algorithm with performance ratio of 3/2 based on the paper of Kubzin.In Chapter five, we study semi-online flowshop scheduling problems with availability constraints. Jobs arrive over a list. The objective is to minimize the makespan. For the problem with an availability constraint on the first machine, we consider an new semi-online model with known the relation between the maximum process time on the first machine amax and the start time s of the non-availability interval, i.e., amax> s, amax<s or amax=s. We prove that the lower bounds are 2 and LS algorithm is the best online algorithm. For the problem with an availability constraint on the second machine, we prove that no on-line algorithm has a constant competitive ratio. At last, we consider a semi-online problem with known optimal value C*max and the end time t of the non-availability interval on the second machine where t is not larger than 1/2C*max. We provide an on-line algorithm with competitive ratio of 3/2.In Chapter six, we study on-line and semi-online single machine scheduling problems with an availability constraint. Jobs arrive over a list. The objective is to minimize the makespan. A non-resumable scenario is assumed. For the on-line version, we prove that the lower bound is 2 and LS algorithm is the optimal algorithm. Then we consider the problem with semi-online condition of knowing the largest job processing time pmax and machine is not available during time period [s,t]. We consider three sub-problems with assumptions of pmax>s, pmax<s and pmax=s. The lower bound of the first two cases are proved to be (?) and 3/2, respectively. The best possible algorithms with competitive ratios of (?) and 3/2 are also given. The problem with pmax=s is proved to be solvable. At last, we prove that no on-line algorithm has a constant competitive ratio for the problem with several availability constraints.