A Study Of Some Scheduling Problems Arising From Contemporary Industries

Scheduling problem is one of the classical combinatorial optimization problems, has received many researcher's attention. Many new models come forth along with the developing of social production. This thesis mainly deals with such contemporary scheduling problems arising from the industries, which are made up of seven chapters. We introduce some related preliminary concepts in Chapter 1. Then we study six scheduling models.Chapter 2 investigates the scheduling problem on 2 identical parallel machines, where each machine has a ready time. The goal is to minimize the maximum machine completion time. We give a linear time approximation algorithm with the worst-case ratio (10/9).In Chapter 3, we consider a single-machine scheduling problem with periodic maintenance activities. The objective is to find a schedule that minimizes the makespan, subject to nonresumable jobs. We first prove that the worst-case ratio of the classical LPT algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case ratio less than 2 unless P = NP, which implies that the LPT algorithm is the best possible.Chapter 4 studies the problem of scheduling jobs with step-improving processing times around a common critical date on a single machine to minimize the makespan. we show it is only ordinary NP-hard. We further present an optimal online algorithm, and a linear time offline approximation algorithm with the worst-case ratio (5/4).In Chapter 5, we discuss the problem of scheduling a set of jobs on a single machine on which a rate-modifying activity may be performed. We study the problems of minimizing makespan and total completion time. We first analyze the computational complexity of both problems for most of the possible versions. Furthermore, for the NP-hard cases of the makespan problem, we present a pseudo-polynomial time optimal algorithm and a fully polynomial time approximation scheme. For the total completion time problem, we provide a pseudo-polynomial time optimal algorithm for the case with agreeable modifying rates.Chapter 6 considers a single-machine scheduling problem in which the processing...