Approximation guarantees of algorithms for fractional optimization problems arising in dispatching rules for INDS problems

作者：Sun Hongtan^*; Sharkey Thomas C

来源：Journal of Global Optimization, 2017, 68(3): 623-640.

DOI：10.1007/s10898-017-0498-9

• Approximation algorithm
• Fractional optimization
• Integrated Network Design and Scheduling
• Complexity analysis

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.

• 出版日期2017-7