WORST-CASE ANALYSIS OF INDEXING RULES FOR SINGLE MACHINE SEQUENCING

スポンサーリンク

概要

• 論文の詳細を見る

• The single machine sequencing problem is considered in which each job has a release date, a processing time, and a delivery time. The objective is to find a sequence of jobs which minimizes the time by which all jobs are delivered. We study priority sequencing rules which use an index to prioritize jobs. In particular, we establish worst-case bounds for families of weighted linear and quotient indexing rules. We also analyze an O(n log n.) dynamic indexing rule A. Two subregions of the admissible input space are identified in which heuristic A has better worst-case performance ratios.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Lai T‐c

  National Taiwan Univ.

• Lai Tsung-chyan

  College Of Management National Taiwan University

関連論文

• AN APPROACH FOR WORST CASE ANALYSIS OF HEURISTICS : ANALYSIS OF A FLEXIBLE 0-1 KNAPSACK PROBLEM
• WORST-CASE ANALYSIS OF INDEXING RULES FOR SINGLE MACHINE SEQUENCING

スポンサーリンク