Dissertation > Excellent graduate degree dissertation topics show

Special sort of parallel work

Author: ZhangKai
Tutor: ZhangGuoChuan
School: Zhejiang University
Course: Operational Research and Cybernetics
Keywords: Parallel work Online scheduling Design and Analysis of Algorithms Competitive Ratio Analysis
CLC: O223
Type: Master's thesis
Year: 2007
Downloads: 33
Quote: 0
Read: Download Dissertation

Abstract


This study are two special cases online (Over List) parallel job scheduling , the goal is the minimum makespan . Parallel Job Scheduling Parallel machine scheduling problem with the general difference is that the workpiece , a workpiece may take several machines simultaneously its processing . Workpiece arrive one by one , and only after the arrival of the workpiece , it requires the number of machines and processing time is known and the workpiece once reached , it must immediately arrange for its processing . The first chapter is the introduction, which focuses on sorting , parallel job scheduling , approximation algorithms and competitive ratio analysis basics. The second chapter of the workpiece non-increasing order by size reaches a parallel job scheduling , first introduced the problem of greedy algorithm (LS), which arranged the workpiece at the earliest possible moment , the algorithm is the upper bound of competitive ratio 11/ 4, the lower bound of competitive ratio is 5 /2. Section II gives an improved greedy algorithm , competitive ratio does not exceed 1 10 1/2 / 2. The third chapter of the workpiece according to the processing time of non-increasing order of arrival greedy algorithm (LS), the upper bound of the algorithm is proved at most two .

Related Dissertations

  1. Optimal Riser Design of Steel Casting Based on CAE Analysis,TG260
  2. Online Parallel Machine Scheduling Problems,O223
  3. The Complexity of Some Batching Scheduling and On-Line Scheduling Problems,O223
  4. Research on Resource Management Mechanism in Open Network,TP393.07
  5. On-line Scheduling on Uniform Parallel Machines,O223
  6. The Scheduling with Rejection and Parallel-batching on Parallel Machines and on-line Scheduling with Parallel-batching on Two Uniform Machines,O223
  7. Workpiece may refuse the online scheduling problem of the two models,O223
  8. Online Scheduling on Parallel-batch Machines and Online Scheduling with Delivery Times,O223
  9. Research of Plant Load Optimal Distribution System,TM621
  10. The Applying of RAGA in the Optimizing Design and Stability Analysis of Deep Foundation,TU753
  11. Semi On -line machine covering research,O223
  12. Similar machine scheduling problem of batch scheduling problem with machine preparation time,O223
  13. Hard Real-Time Communication Protocol Design and Implementation Based on Ethernet,TP393.04
  14. Fixed workpiece online scheduling problems with multiprocessor tasks,O223
  15. Competitive Analysis on Semi-online Scheduling Algorithms for Single-machine Problems,O226
  16. Parallel to the plane of the workpiece with the arrival time online and semi- online scheduling problems,O223
  17. On-line approximation algorithm for sorting number of studies,O223
  18. Online Scheduling on Parallel Batch Machine(s),O223
  19. Research on Data Center Structure and Scheduling Mechanism in Cloud Computing,TP308
  20. Algorithm Research for Some Flowshop Scheduling Problems,O223

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