Dissertation > Excellent graduate degree dissertation topics show

Two Approximate Algorithms for Scheduling Jobs on Parallel Machines with a Single Server

Author: ZhouYing
Tutor: SuChunJie
School: East China University of Science and Technology
Course: Applied Mathematics
Keywords: Schedule Parallel machines Server Approximate algorithm Worst case ratio
CLC: O223
Type: Master's thesis
Year: 2012
Downloads: 19
Quote: 0
Read: Download Dissertation

Abstract


In this paper, we consider the problem of scheduling jobs on parallel machines with a single server. It is a generalization of the classic parallel machines scheduling problem. In this problem, a job must be setup onto a machine by a server before it is processed by the machine. The server can only setup one job at one time. The objective is to minimize the maximal job completion time (makespan). We present an approximate algorithm with the worst case ratio 4/3 for the case of two parallel machines, where all the jobs’ setup times are equal. When there are three parallel machines and all the jobs’setup time are equal to one, we also present an approximate algorithm with the worst case ratio 3/2.

Related Dissertations

  1. The Research and Design of Middle-Small Enterprises Purchase-Sales-Inventory Management System,TP311.52
  2. Grass-roots forces the day-to-day management of information systems design and implementation,TP311.52
  3. Animal products quality safety and security regulation of RFID systems,TS201.6
  4. XA city administrative center of e-government network construction project schedule management,D630
  5. Design and Implementation of the Online Map System Based on LBS,TN929.5
  6. Heilongjiang Unicom WCDMA network project schedule management research,F626
  7. Design and Application of Vending Machine Wireless Communication Based on eCos,TH692.6
  8. The Rearch of the WLAN Project Schedule Control in HZ Company,TN925.93
  9. Based on B / S Three-tier Warehouse Management System Design and Implementation,TP311.52
  10. Based on the Introduction of University Teaching Management System Design and Implementation,TP311.52
  11. A Video Monitoring System for Anshan Power Supply Room,TP391.41
  12. Progress Control Research of GS Building,TU722
  13. Government ( police ) department Network Video Monitoring System Design and Implementation,TP277
  14. The Design and Implementation of the real estate project management system,TP311.52
  15. A Research on the Schedule Management of X Nuclear Power Project,F426.23;F426.61
  16. Video Multiplexer FPGA-based SOPC Design and Implementation,TN949.197
  17. The Design and Implementation of Digital Video Server Based on DM6467,TP393.05
  18. Research on Resource-constrained Project Scheduling with Critical Chain for Multi-project,F272
  19. The Design and Implementation of Monitoring System Based on Embedded Web Server in Portable Satellite Communication Earth Station,TN927.2
  20. Project Management in Asian communication support of applied research,F626
  21. Domestic IDC analysis of the construction project schedule management,F49

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