The Study On Three Single-Machine Scheduling Problems Under Constraint Relationships

Scheduling is one kind of important combinatorial optimization problem, which use some processors, machines or resources to accomplish optimally a batch of given tasks or jobs.According to the number of processors, scheduling problem can be grouped as single-machine scheduling problem and multi-machine scheduling problem. According to whether the job's processing time, released time and the surroundings of the processors are deterministic or stochastic, scheduling problem can be grouped as deterministic scheduling problem and stochastic scheduling problem. According to whether the parameters of the jobs are given before-hand, scheduling problem can be grouped as static scheduling problem and dynamic scheduling problem.Many constructive results on scheduling problems have been given out by now. But there are still a large quantity of problems that are not resolved.In 1978, an algorithm for minimizing total weighted completion time with a series-parallel precedence was given by Lawler. In 1998 a weighted discountedmaximum p -factor chain rule for the problem 1|chains|∑WJ(1-e-rCj) was given to get the optimal scheduling by Ruo Chengxin and Zhao Yufang.In 1977, some dominance theorems for the problem 1|rj|∑wjCj was givenby G. Rinaldi and A. Sassano. From then on, some other new dominance theorems, branch and bound algorithms was given constantly.In 1997, two preemption models and on-line optimal dispatching rules of dynamic single-machine scheduling problems which object functions were minimizing total flow time and minimizing weighted flow time respectively was given by Julien et al.This thesis studies the following three single-machine scheduling problems: 1) The scheduling problem 1|sp-graph\∑wj(1-e-rCj) is studied. We showthat under the consideration of discounted factor, jobs in the p -maximalinitial set/* of module M should be processed prior to other jobs in module M, and the schedule is the optimal if the jobs in I* aren't be preempted by thejobs in N\ I*. This result is a extension of Lawler's method for minimizing total weighted completion time with a series-parallel precedence.2) The scheduling problem 1 |rj|∑wjCj, is studied. Firstly, We develop a newheuristic algorithm. Then we develop the crossover and mutation operator by defining jobs' two neighborhoods, and we solve this problem with genetic algorithm. Compared with traditional heuristic algorithms, the result given by genetic algorithm is closer to the optimal solution. And compared with branch and bound algorithms, the genetic algorithm needs a relative fewer time.3) The on-line scheduling problem with constrains relationship is studied. We use generalized preemption models to study the dynamic single-machine scheduling problems of minimizing total weighted completion time and develop on-line optimal dispatching rules, which consider only available information.