Approximation guarantees of algorithms for fractional optimization problems arising in dispatching rules for INDS problems |
| |
Authors: | Hongtan Sun Thomas C. Sharkey |
| |
Affiliation: | 1.Department of Industrial and Systems Engineering,Rensselaer Polytechnic Institute,Troy,USA |
| |
Abstract: | In this paper, we provide approximation guarantees of algorithms for the fractional optimization problems arising in the dispatching rules from recent literature for Integrated Network Design and Scheduling problems. These fractional optimization problem are proved to be NP-hard. The approximation guarantees are based both on the number of arcs in the network and on the number of machines in the scheduling environment. We further demonstrate, by example, the tightness of the factors for these approximation algorithms. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|