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

Abstract

在生產排程領域中，排序與排程有不同意涵。所謂排序是指決定每個機器上的工作順序；排程則必須更精確設定每項作業在每臺機器上之開工時間點。過去的文獻顯示中，在給定工作順序後，可以很快地求取最佳化之排程。然而，我們發現有許多問題並非如此。本計畫第一年已討論多個排程問題，假設部分機器之工作順序已經給定，我們必須求出最佳排程。資源限制下多機排程，我們已設計三個目標式之動態規劃演算法，其複雜度為polynomial。對於與交期有關之兩項目標式，我們證明為NP-hard，此為排程理論中很特殊之現象。另外針對其他問題，我們亦設計了動態規劃演算法。

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 the first year of this project, we investigated several scheduling problems with the assumption of fixed job sequences. We developed efficient dynamic programming algorithms for the resource-constrained problems of three different objective function. For two other due-date related objective functions, we successfully establish their NP-hardness. Our results also include several polynomial-time dynamic programming algorithms.