Dissertation > Excellent graduate degree dissertation topics show

Some Results on Parallel Machine Scheduling Problems

Author: ChengZhenMin
Tutor: LiHongXing
School: Beijing Normal University
Course: Applied Mathematics
Keywords: parallel scheduling objective algorithm makespan total comple-tion time release time preemption periodic maintenance
CLC: O223
Type: PhD thesis
Year: 2008
Downloads: 300
Quote: 1
Read: Download Dissertation


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.

Related Dissertations

  1. Research on Scheduling of Whole-set Orders in JSP Based on Differential Evolution Algorithm,F273
  2. Research on Graph-Based Algorithm for Tagsnps Selection,Q78
  3. Research and Realization on Synchronization Technology of High Sensitivity GNSS Software Receiver,P228.4
  4. Development of the Platform for Compressor Optimization Design and Aerodynamic Optimization Design in the Transonic Compressor,TH45
  5. Effectiveness Evaluation on the Jointed Combat of the Multiple Missiles and Research on Combinatorial Optimization Algorithm,TJ760.1
  6. The Inductive Load Based Vehicle Body Network Control System,U463.6
  7. Reseach on Optimal Control of Elevator Group Based upon Ant Colony Algorithm,TU857
  8. Research on Temprature Controling Technology of Laser Diode with Thermoelectric Cooler,TN248.4
  9. The AES Algorithm and Its Implementation in DSP,TN918.1
  10. Research on UWB Location Technology Using UWB Radio Signal,TN929.5
  11. The Algorithm of DFT with a Subset of Output Points Based on TS101 and Its Software Implementation,TN911.72
  12. Study on Estimation of Two Dimensional Direction of Arrival Using a DBF Receiver,TN851
  13. Optimizing and Realising Research on Vedio Compression in TV Guidance System,TN919.81
  14. Study on Channel Coding Algorithm in IEEE802.16e,TN911.22
  15. Research on Decoding Algorithm for LDPC Codes,TN911.22
  16. Research on Parallel Frequent Graph Pattern Mining,TP311.13
  17. The Fatigue State Recognition of the Driver Based on Eye Detection,TP391.41
  18. Research and Implementation on Content-Based Clothing Image Retrieval,TP391.41
  19. Research on Removal Algorithm of Shadows in Image Segmentation,TP391.41
  20. Research on Navigation System Related Technology for Moving Objects under Dynamic Environment,TP301.6
  21. Research and Implementation for Method of AUTOSAR System Modeling,TP311.52

CLC: > Mathematical sciences and chemical > Mathematics > Operations Research > An integrated approach
© 2012 www.DissertationTopic.Net  Mobile