Scheduling Problems With Delay Time

Scheduling problem is a kind of important combinatorial optimization problem. In recent years, many scholars take it seriously. At the same time, there are many new models in the theory and practical aspects. Among them, the multiple operations scheduling problems have new application background. Usually, it is assumed that the later operations can be processed at any time after the earlier operations are finished. However, in many practical systems, there must exist certain delay time between two adjacent operations. In this thesis, we mainly study the scheduling problems with delay time.The thesis is split up into four chapters. In chapter1, we introduce some preliminary concepts related to scheduling problems and then summarize the previous results.In Chapter2, we study the single machine scheduling where the job has two processes. The first one of the job should be processed before the second one. Further, there is at least a lag l(0≤l≤1) between the start time of the second process and the completion time of the first process. It is called delay time. The goal is to minimize the total completion time of all jobs. Both two processes have a unit processing time in this paper. According to the size of the delay time, we present the optimal schedules for both cases of l∈[0,1/3) and l∈[1/3,1).In chapter3, we study the scheduling problem with exact delay time, i.e., the delay time become exactly l unit time between the first operation and the second operation. All the operations are the same (aj=bj=a) and the delay time is integral multiple of the processing time of operation (l=ka). The goal is to minimize the total weighted completion time. We present optimal schedules for both single machine scheduling and two-machine flow shop.In chapter4, we summarize this thesis and give the prospect of further study.