準備時間と先行制約を伴う並列機械スケジューリング問題の近似解法について

概要

論文の詳細を見る
This paper discusses a parallel-machine scheduling problem where many jobs are scheduled on identical parallel machines so as to minimize the maximum lateness under precedence constraints given by partial order, each job having an arbitrary ready time, a unit processing time and an arbitrary due date. This problem is well known to be NP-complete, strongly suggesting the intractability of the problem. Thus this paper aims to get excellent approximation algorithms for the problem. First, some practical meanings of the model are discussed, and properties of the problem useful for approximation algorithms are shown. Then approximation algorithms based on some heuristics are proposed, and their performances are analyzed both theoretically and experimentally, showing in result the superiority of one of the proposed algorithms.
1988-01-25