Design And Analysis Of Algorithms For Some Modern Scheduling Problems

In this thesis, we consider some modern scheduling problems, including scheduling problems with rejection, scheduling problems with availability constraint and automated storage and retrieval system with stacker cranes on one rail, which is derived from to-bacco industry. We study properties of these problems, design algorithms and analyze these algorithms by giving performance ratio, competitive ratio or conducting numerical simulations. The thesis consists of six chapters.In Chapter 1, we introduce the background of combinatorial optimization and schedul-ing problems. We also present some preliminary concepts and definitions involved in the thesis. Literature reviews are conducted for classical and online scheduling problems as well as scheduling problems with rejection or with availability constraint.In Chapter 2, we study scheduling problems with rejection for both single machine and identical machines. In the single machine problems, each job has penalty a times of its processing time. If jobs have various release dates, the problem of minimizing the sum of makespan and total penalty can be solved in polynomial time. If jobs have same release date, the problem of minimizing the sum of total completion time and total penalty also can be solved in polynomial time. In the identical machines problems, jobs arrive at two different arrival times. We design on-line approximation algorithms with competitive ratios 2 and 4 - 2/m for the two cases when the number of machines is two and m, respectively.In Chapter 3, we consider a two-machine flow shop scheduling problem with rejection. Each job has two operations that could be processed on machines or rejected with penalty, respectively. Operations on the first machine have penalties α1 times of their processing times and operations on the second machine have penalties α2 times of their processing times. The objective is to minimize the sum of makespan of accepted operations and total penalty of rejected operations. A 4/3-approximation algorithm is presented for the case where min{α1,α2}<1 and max{α1,α2}≥1. For general α1 and α2 we design two dynamic programming algorithms with different computation times and fully polynomial- time approximation schemes (FPTAS).In Chapter 4, we focus on the semi-online single machine scheduling problems with availability constraint. The machine has one unavailable interval because of maintenance or breakdown. Jobs arrive over time and cannot be processed in the unavailable interval. The objective is to minimize the makespan. In these semi-online problems, some infor-mation is known in advance, such as the largest processing time, the sum of all processing times, the largest arrival time or the optimal makespan. For these semi-online problems, we give their lower bounds, design semi-online algorithms and prove their competitive ratios.In Chapter 5, we consider an on-line scheduling and routing problem concerning automated storage and retrieval system from tobacco industry. In this problem, two stacker cranes run one common rail between two racks. Two stacker cranes should keep at a safe distance. Two racks with equal-sized cells are along the rail. Multiple input/output-points are located at the bottom of racks. Requests of transporting bins are generated over time. Stacker cranes transport bins between input/output-points and cells on racks. The objective is to satisfy manufacturing requirements and minimize the time by which all the generated requests are completed. It can be considered as an on-line scheduling and routing problem. Under given physical layout, we prove the NP-hardness of the problems and design on-line control strategies for both one-stacker-crane model and two-stacker-crane model. Instances and numerical simulations are presented to evaluate the validity of the on-line algorithms. The algorithms have been implemented and received positive feedback.In Chapter 6, we conclude research results and present several directions for future research.