Dissertation > Excellent graduate degree dissertation topics show

The Study of Some Scheduling Problems with Competing Agents

Author: WangJieMing
Tutor: LuXiWen
School: East China University of Science and Technology
Course: Applied Mathematics
Keywords: agent scheduling approximation algorithm performance ratio
CLC: O223
Type: Master's thesis
Year: 2011
Downloads: 10
Quote: 0
Read: Download Dissertation

Abstract


In this paper, we consider some scheduling problems with competing agents. There are two agents. They have a number of jobs which were processed common in the machines. We study the constrained optimization problem model. Objective is to minimize one agent’s makespan under the other agent’s makespan satisfying constainted condition.We dicuss two versions of release time or not.we prove that the problems are NP-hard.We present the approximational algorithms and analysis the performance ratio of the algorithms in the worst case.For the case of no release time, we assume that jobs of one of the agents must be processed on m machines. In response to this situation, we propose an approximational algorithm, and show that the performance ratio of the algorithm is 2-1/2m, and give a tight instant.For the situation with the realease time, we study the cases of preemption or not. Assuming that the jobs of one agents must be processed on m machines, and the other agent’s jobs are processed on mi(1≤mi≤<m) machine simultaneously. For the case of preemption, we give an algorithm based on the number of list processing machine sorting.We show that the performance ratio of the algorithm in the worst case is 2-1/m, and prove the bound is tight. For the case of nonpreemption, we think the optimization vaule is at least twice of the case of the preemption.We also disscuss the complexity of the jobs’processing time which can be controlled with competing agents.

Related Dissertations

  1. Research on Scheduling of Whole-set Orders in JSP Based on Differential Evolution Algorithm,F273
  2. Construction and Performance Analysis for In-Vehicle FlexRay Backbone Network,TP273
  3. Design and Implementation of Automotive Can-Can Gateway,TP273
  4. The Problems and Countermeasures in Respect to Agent Construction of the Project: Guangzhou Asian Games Venues,G812.2
  5. "Social Agent": between Active and Inactive,D625
  6. Research and Implementation on Service-Oriented Multi-Agent System Cooperation Mechanism,TP393.09
  7. The Preparation of Aluminum-Ammonium Cationic Starch and Its Application in Papermaking,TS727
  8. Research of Scheduling Algorithm Based on Hybrid Adaptive Genetic Algorithm in Computing Grid,TP393.09
  9. Research of Communication Mechanism in the Distributed Network Based on Mobile Agent,TP393.02
  10. The optimal scale of investment of private equity funds,O224
  11. Preliminary Study on Obstacles Effect of Succession Cropping and Reduction Techniques of Microbial Agents in Flue-cured Tobacco,S572
  12. Public Transport Optimal Dispatching Based on the Genetic-Newton Algorithm,TP18
  13. Effect of Flue-cured Tobacco Continuous Cropping on Soil Chemical and Physical Properties and Tobacco Leaf Quality,S572
  14. Research on Agent Construction System Management Model of Highway Project,F283
  15. A Research on Soil Transmission Medium of Rice Stripe Virus,S435.111.42
  16. A Research on Soil Transmission Medium of Rice Stripe Virus,S435.111.42
  17. Cultured Bacillus Japanese beetles and freeze-drying protectants recovery of,S482.3
  18. Nano LaFeO 3 Controllable Synthesis and TiO 2 bridged construct composite photocatalyst,O643.36
  19. Zhang Antai Sue Construction Bank Branch of Baiyin Infringement Case Analysis,D923
  20. Heat Resistant Research of Biodegradable Polylactic Acid Materials,TQ320.7
  21. Research of the Relationship between Clan System and Principal-agent Relationship in Huizhou Pawnshops,K248

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