947. Multiprocessor job scheduling with increasing the number of machines
Invited abstract in session MB-12: Scheduling models and algorithms, stream Scheduling and Project Management.
Monday, 10:30-12:00Room: Clarendon SR 1.02
Authors (first author is the speaker)
| 1. | Tao Sun
|
| Department of Industrial Engineering, Northwestern Polytechnical University |
Abstract
A multiprocessor job is the job that requires simultaneously more than one machine for its processing. For the multiprocessor job scheduling problem with minimizing the makespan, the impact of increasing the number of machines on the makespan is analyzed, the best-case impact ratio for the optimal schedule and that for approximation schedules are proved, and the law that the makespan decreases and trends toward stabilization as the number of machines increases is revealed. Furthermore, increasing the number of machines results in a decrease in the makespan and an increase in the machine costs. The trade-off between the decrease in the makespan and increase in the machine costs is analyzed, and the number of machines is determined to minimize the weighted sum of the makespan and the machine costs. An approximation algorithm based on the first fit decreasing algorithm is designed to obtain the schedule. The worst-case performance ratio of the approximation algorithm is proven to be no greater than 2. The simulation results show the effectiveness of the best-case impact ratios for the approximation schedules and the worst-case performance ratio of the designed approximation algorithm.
Keywords
- Scheduling
Status: accepted
Back to the list of papers