PERFORMANCE ANALYSIS OF SIX APPROXIMATION ALGORITHMS FOR THE ONE-MACHINE MAXIMUM LATENESS SCHEDULING PROBLEM WITH READY TIMES

DOI Web Site 3 Citations Open Access

Bibliographic Information

Other Title
  • 最大納期遅れを最小にする1機械処理順序問題に対する6種の近似解法の評価 : 準備時間のある場合

Search this article

Description

Six approximation algorithms for the one-machine scheduling problem with ready and due times to minimize the maximum lateness are analyzed. The performance is measured by the relative deviation of approximate values to optimal ones. Best possible upper bounds on the worst case performance of all six algorithms are derived. The average performance is also examined by solving randomly generated problems; one of the six algorithms outperforms others and keeps the average relative deviation within 2%.

Journal

Citations (3)*help

See more

Details 詳細情報について

Report a problem

Back to top