給定作業順序下排程問題複雜度探討與演算法設計

Abstract

在生產排程領域中，排序與排程有不同意涵。所謂排序是指決定每個機器上的工作順 序；排程則必須更精確設定每項作業在每臺機器上之開工時間點。過去的文獻顯示中， 在給定工作順序後，可以很快地求取最佳化之排程。然而，我們發現有許多問題並非 如此。本計畫提出四個排程問題，假設部分機器之工作順序已經給定，我們必須求出 最佳排程。計畫中，我們首先要確認各項研究問題之時間複雜度，所涉及的研究方法 為提供NP-hardness 證明以及設計多項式動態演算法。我們將運用所設計之動態規劃演 算法求取原題目的下界值。另外，我們也將設計簡潔之經驗法則演算法以及近似規劃， 我們的研究重點將著重於分析其誤差與效能。

In the context of scheduling theory research, sequencing and scheduling have different interpretations as well as different implications. Sequencing refers to the decision about how to determine the processing order of jobs/operations on all machines involved. Scheduling demands that the starting times (or, completion time) of all jobs/operations must be clearly specified. In most scheduling problems, schedules can be easily derived if job/operation sequences on the machines are known a priori. Nevertheless it is not the case for some scheduling problems. In this project, we propose four scheduling problems with the assumption of fixed job sequences. We will develop efficient dynamic programming algorithms for the problems that are polynomially solvable. On the other hand, we will present NP-hardness proofs of the problems that we fail to design efficient dynamic programs. The proposed efficient dynamic programming algorithms will be deployed, incorporating the data rearrangement technique, to produce lower bounds on the optimal solutions of the original problems without fixed job sequences. For the hard problems subject to fixed job sequences, we will address the inapproximability of the problems and design approximation algorithms and analyze their performance ratios.