Some Problems In Scheduling Where Jobs Can Be Preprocessed And Semi-Hybrid Flowshop Problem

In this thesis, we study two scheduling problems. One is a single machine scheduling where jobs can be preprocessed, the other is a special hybrid flowshop problem, called semi-hybrid flowshop problem. For both problems, we study their computational complexity and present optimal algorithms or polynomial time approximation algorithms. The thesis consists of three chapters.In chapter 1, we give some introduction and preliminaries for scheduling problems.In chapter 2, we investigate a single machine scheduling where jobs can be pre-processed before they are scheduled on the machine. The objective is to minimize the cost for preprocessing under the constraint that no job is tardy. We show this problem is NP-hard and present a pseudo-polynomial time algorithm. For the case that the costs for preprocessing jobs are the same, we present a strongly polynomial time algorithm.In chapter 3, we consider a two-stage semi-hybrid flowshop problem which appears in graphics processing. This problem can be divided into two problems by between two stages the waiting is allowed or not: waited model and no-waited model. For the waited model, we show that it is NP-hard, and present an optimal pseudo-polynomial time algorithm and an approximation algorithm with worst-case ratio 3/2 + 1/(10). For no-waited model, we show it is strongly NP-hard, and present a pseudo-polynomial time optimal algorithm and an approximation algorithm with worst-case ratio 5/3.