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 completion time release time preemption periodic maintenance
CLC: O223
Type: PhD thesis
Year: 2008
Downloads: 300
Quote: 1
Read: Download Dissertation
Abstract
With the development of production and the increasing international connection,the theories and applications of scheduling have been developed rapidly. It is a form ofdecisionmaking that plays an important role in manufacturing and service industries.Scheduling problems is an important branch of optimization research. Scheduling theory comes from all kinds of real life scheduling models. Problems studied within theframework of that theory have numerous applications in various fields of human activity. 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 nonpreemptive case, respectively. They are both NPhard problems. For theformer problem, an approximation algorithm is proposed. The worstcase bound ofthe algorithm is 2(n1)/nfor the problem, it is better than the current approximationalgorithm which has the worstcase bound 2. For the nonpreemptive case, based onthe algorithm we proposed and algorithm CONVERT, an algorithm is considered withthe worstcase bound is 6(n1)/n.Then the three parallel machines scheduling problem with preemptions and releasetimes to minimize total completion time is considered. It is an NPhard problem. Aheuristic algorithm is given. The worstcase performance bound is 32 for the problem, it is better than the current approximation algorithm with the worstcase 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 ASRPTFM andprove that it can generates an optimal schedule for the scheduling problem.In the third part, the two machines parallel scheduling problem with periodic maintenance 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 NPhard problem. We give the worstcase 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 worstcase bound of the classical LPTalgorithm is 3/2 if the problem is o?line and the worstcase 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 basedMoorealgorithm is proposed, and the algorithm can get an optimal schedule.

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