Dissertation > Excellent graduate degree dissertation topics show

The Scheduling with Rejection and Parallel-batching on Parallel Machines and on-line Scheduling with Parallel-batching on Two Uniform Machines

Author: RenLiLi
Tutor: YuanJinJiang
School: Zhengzhou University
Course: Operational Research and Cybernetics
Keywords: Online scheduling Competitive ratio Consistent batch machine
CLC: O223
Type: Master's thesis
Year: 2010
Downloads: 14
Quote: 0
Read: Download Dissertation

Abstract


Parallel batch sequencing is an important model of a modern sorting its advantage is that the plurality of workpieces can be placed in the same batch to be processed at the same time , thereby improving work efficiency wherein a workpiece batch processing time is defined as the longest group contains processing times of jobs in this article , we study two types of parallel batch scheduling problem . First, we studied the workpiece arrival time and may refuse on m unbounded parallel batch scheduling problem of parallel processors to minimize makespan . the problem , if you reject a workpiece , then take some punishment costs ; accept this workpiece , the workpiece is assigned to m machines on stage batch processing . objective function is to minimize the workpiece costs and completion time and refused workpiece when m is a given constant , we have given this issue a pseudo- polynomial time algorithm and a fully polynomial-time approximation scheme . Secondly, we study consistent online batch machine to minimize makespan scheduling problem in the problem , we have two batch machine , the speed of the machine is a another machine speed v , where 0 lt ; v ≤ 1 . All the workpiece are following time line to reach , in the workpiece prior to the arrival of their message , we know nothing about . assuming α ≈ 0.618 is the positive root of the equation α2 α-1 = 0 , and β β3 3β2 equation (3-1 / v) β-1 / v = 0 the positive root of the problem , we first establish its competitive than the lower bound : 1/2 ≤ v ≤ 0 lt; v ≤ 1/2 , the lower bound of 1 α; 1 , the lower bound of 1 β. above the lower bound of pj = 1 case also established . Secondly , we present two online algorithms Delay-Q2 and Refined - Delay - Q2 . online algorithm Delay- Q2 competition ratio of max {1 α, min {1 v, 1 / v α}}. 0 lt; v ≤ 1/2 , the online algorithm is the best possible , and pj = 1 is the best possible competitive ratio are 1 α ≈ 1.618. when 1/2 ≤ v ≤ 1 , and pj = 1 , online algorithm Refined-Delay-Q2 is the best possible , the competition ratio of 1 β . Thus, pj = 1 case , the study The problem has been the complete solution .

Related Dissertations

  1. Workpiece may refuse the online scheduling problem of the two models,O223
  2. Workpiece parallel machine online scheduling problem with precedence constraints,O223
  3. Online Scheduling of Unit Length Jobs on a Batching Machine to Maximize the Number of Early Jobs,O223
  4. On-line Scheduling on Partial Batch-machine,O223
  5. And so long workpieces online scheduling batches under Order Restriction,O223
  6. Parallel Machine Scheduling with Chains Precedence Constraints,O223
  7. On-line Parallel Machine Scheduling with Chains Precedence Constraints,O223
  8. Two Special Models of On-line Batch Scheduling,O223
  9. Semi-on-line Scheduling on Parallel Machines with Non-simultaneous Machine Available Times,O223
  10. Two Models on Batch Scheduling of Weighted Sum Objectives,O223
  11. Online Scheduling Problem with Delivery Times of Jobs,O223
  12. On-line Scheduling on Batch Machines with Lookahead,O223
  13. Online-list Scheduling on a Bounded Batch Machine,O223
  14. Scheduling on a Batch Processing System with Item-availability to Minimize Total Weighted Job Completion Time,O223
  15. Online Serial-batch Scheduling and Off-line Mixed Batch Scheduling on a Single Machine,O223
  16. Scheduling in Group Technology and Online Supply Chain Problem,O223
  17. Some Scheduling Problem in Production Management,O223
  18. The Study of Competitive Decision-making Algorithm for Online Currency Trading,F830
  19. Two Batch Scheduling Models with Family Jobs,O223
  20. On-line Scheduling on Uniform Parallel Machines,O223

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