原文传递
Parallel machine scheduling by column generation
| 题名： | Parallel machine scheduling by column generation |
| 作者： | J.M. van den Akker, J.A. Hoogeveen, S.L. van de Velde |
| 关键词： | Air traffic control Air traffic Algorithms Arrivals Cost reduction Linear programming Parallel processing (computers) Run time (computers) Scheduling Tasks Weighting functions |
| 摘要： | Parallel machine scheduling problems concern the scheduling of n jobs on m machines to minimize some function of the job completion times. If preemption is not allowed, then most problems are not only NP-hard, but also very hard from a practical point of view. In this paper, we show that strong and fast linear programming lower bounds can be computed for an important class of machine scheduling problems with additive objective functions. Characteristic of these problems is that on each machine the order of the jobs in the relevant part of the schedule is obtained through some priority rule. To that end, we formulate these parallel machine scheduling problems as a set covering problems with an exponential number of binary variables, n covering constraints, and a single side constraint. We show that the linear programming relaxation can be solved efficiently by column generation, since the pricing problem is solvable in pseudo-polynomial time. We display this approach on the problem of minimizing total weighted completion time on m identical machines. Our computational results show that the lower bound is singularly strong and that the outcome of the linear program is often integral. Moreover, they show that our branch-and-bound algorithm that uses the linear programming lower bound outperforms the previously best algorithm. We elaborate on the application of the presented approach to parallel machine scheduling problems other than that of minimizing total weighted completion time on identical machines. Moreover, we discuss the occurrence of parallel machine scheduling problems in the field Air Traffic Management (ATM) and investigate the applicability of the approach to problems in this field. |
| 报告类型： | 科技报告 |
相关文献
- A real time bus dispatching and rescheduling system.
- FABRICATION AND TESTING OF AN AUTOMATED CRACK SEALING MACHINE.
- Massively Parallel, Adaptive, Color Image Processing for Autonomous Road Following.
- MACHINE LEARNING IN UPDATING PREDICTIVE MODELS OF PLANNING AND SCHEDULING TRANSPORTATION PROJECTS.
- DESIGN AND IMPLEMENTATION OF PARALLEL DYNAMIC SHORTEST PATH ALGORITHMS FOR INTELLIGENT TRANSPORTATION SYSTEMS APPLICATIONS.
- Massively Parallel Modeling and Simulation of Next Generation Hybrid Neuromorphic Supercomputer.
检索历史
应用推荐
