Some Results On Parallel Machine Scheduling Problems

With the development of production and the increasing international connection,the theories and applications of scheduling have been developed rapidly. It is a form ofdecision-making that plays an important role in manufacturing and service industries.Scheduling problems is an important branch of optimization research. Scheduling the-ory comes from all kinds of real life scheduling models. Problems studied within theframework of that theory have numerous applications in various fields of human ac-tivity. In the current competitive environment e?ective sequencing and scheduling hasbecome a necessity for survival in the marketplace.In this thesis, some parallel machine scheduling models are analyzed in details.During this paper, several di?erent objectives are considered. The three principalobjectives are the minimization of the makespan, the total completion time and thetotal number of tardy jobs. The parameters may be deterministic or fuzzy. Once thejobs have release time in parallel machine schedule, it becomes more di?cult to dealwith. However, preemptions may provide an advantage when the jobs are not releaseat the same time. It contains the following innovative results.In the first part, firstly, we consider the two parallel machines scheduling problemwith release times to minimize the total completion time the preemptive case andthe non-preemptive case, respectively. They are both NP-hard problems. For theformer problem, an approximation algorithm is proposed. The worst-case bound ofthe algorithm is 2(n-1)/nfor the problem, it is better than the current approximationalgorithm which has the worst-case bound 2. For the non-preemptive case, based onthe algorithm we proposed and algorithm CONVERT, an algorithm is considered withthe worst-case bound is 6(n-1)/n.Then the three parallel machines scheduling problem with preemptions and releasetimes to minimize total completion time is considered. It is an NP-hard problem. Aheuristic algorithm is given. The worst-case performance bound is 32 for the problem, it is better than the current approximation algorithm with the worst-case bound 2. Thenwe consider the linear programming formulation for the problem. At last, we give anapproximation algorithm for the the unrelated parallel machines scheduling problemwith preemptions and release times to minimize total completion time.In the second part, the parallel machine scheduling problem with preemption andrelease time is considered, the objective is to minimize makespan. Firstly, an optimalalgorithm is proposed to solve the identical parallel machine scheduling. Then for theunrelated parallel machine scheduling, we propose another algorithm ASRPT-FM andprove that it can generates an optimal schedule for the scheduling problem.In the third part, the two machines parallel scheduling problem with periodic main-tenance is considered. there are few papers on the topic in the scheduling literatures.Firstly, we consider the problem where two machines need periodic maintenance. Itis an NP-hard problem. We give the worst-case bound analysis of the classical FFDalgorithm for the problem with the maintenance time t≤T/3. Then the schedulingproblem where one machine is periodically unavailable with the objective of minimizingmakespan is considered. It is showed that the worst-case bound of the classical LPTalgorithm is 3/2 if the problem is o?-line and the worst-case bound of the LS algorithmis 2 if the problem is online.In the fourth part, the parallel scheduling problems with fuzzy parameters areconsidered. Firstly, the parallel machine scheduling problem with fuzzy processingtime to minimize the total completion time is considered, an approximation algorithmis proposed to solve the problem. Then for the parallel machine scheduling problemwith fuzzy due dates to minimize the total number of lateness, an algorithm basedMoore-algorithm is proposed, and the algorithm can get an optimal schedule.