Dissertation > Excellent graduate degree dissertation topics show

Two Uniform Machines Maximizing the minimum load machine Issues

Author: ChenXingZuo
Tutor: TanZhiZuo
School: Zhejiang University
Course: Operational Research and Cybernetics
Keywords: Similar machine Processing time LPT algorithm Worst-case Competitive ratio Lower bound
CLC: O223
Type: Master's thesis
Year: 2008
Downloads: 19
Quote: 0
Read: Download Dissertation

Abstract


In this thesis two uniform machines maximize the minimum load machine scheduling problem . Model requires that the ratio of the two speeds is q workpiece on the machine , and can not be interrupted when the workpiece is known , the goal is to make the smallest machine load to maximize its processing time . This paper analyzes the use LPT algorithm for solving offline model worst-case , worst-case proof is given bound is tight instance. Secondly, the half- known Time Jobs online model, we LPT algorithm based on certain range segment q reach the lower bound of the problem situation , the design of the optimal algorithm and prove its competitive ratio . And competition among the worst-case ratio parameter q are represented as piecewise functions . Finally, at different intervals on the segment q, q are given in order to illustrate examples as a function of the lower bound of half -line problem , from a competition point of view than the algorithm is proved optimality . Text is divided into three chapters , the first chapter introduces the papers used in sorting knowledge and relevant research results ; second chapter introduces the LPT algorithm worst-case proof of ideas and specific certification process ; chapter describes the optimal algorithm and the proof of the lower bound of the problem .

Related Dissertations

  1. A Smoothing Method for Solving Model under WCVarR,O224
  2. Visual landing guidance UAV pose estimation problem in the study,V249.32
  3. Bring Lower Bounds for Equilibrium Problems Existence of Solutions Xing , stability analysis and Its Algorithm,O177
  4. Eigenvalue problem of a compact Riemannian manifold research,O186.12
  5. Two Parallel Machines Scheduling with a Potential Machine Release Time,O223
  6. Some Tardiness Problems with Machine Disruption,O223
  7. Workpiece may refuse the online scheduling problem of the two models,O223
  8. Workpiece parallel machine online scheduling problem with precedence constraints,O223
  9. On-line Scheduling on Partial Batch-machine,O223
  10. And so long workpieces online scheduling batches under Order Restriction,O223
  11. The Influence of Treatment Time on Meliorating the Interfacial Adhesion Property of the Kevlar 49/ Epoxy Treated by Helium Plasma,TS195.6
  12. Across two-way hollow plate structure finite element analysis,TU375.2
  13. A continued fraction linear lower bound of research and types of proxy signature scheme design,TN918.1
  14. Continued fraction linear lower bound on the number of identity-based signature,TN918.1
  15. Analysis on the Error of Single/Multiple Airborne Observer(s) Passive Localization,TN97
  16. On Algebraic Immunity and Extended Algebraic Immunity of Boolean Functions,TN918.1
  17. Problems on Feedback with Carry Shift Register,TN918.1
  18. Parallel Machine Scheduling with Chains Precedence Constraints,O223
  19. On-line Parallel Machine Scheduling with Chains Precedence Constraints,O223
  20. Two Special Models of On-line Batch Scheduling,O223
  21. Semi-on-line Scheduling on Parallel Machines with Non-simultaneous Machine Available Times,O223

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