非同時到達工件之單機排程--以總加權完工時間最小為目標

Single Machine Scheduling With Unequal Release Date to Minimize Total Weighted Completion Time

陳振男(Jan-Nen Chen)

指導教授 ： 張百棧

元智大學/工程學院/工業工程與管理學系/碩士(1993年)

摘要

本研究探討的，是在單機排程問題中，當工件有不同的到達時間，要求工
件加權完工時間和最小之問題，此為一 NP 艱難的問題。若我們以不同的
權數表示工件的重要性時，求取工件加權完工時間和最小之問題，相當於
使在製品庫存之成本最低。在某些情況下，這類的問題可加以分解成數個
子問題，再以分枝界限法分別求解。本文首先在理論上證明對任一工件集
而言，其WSPT排程的完工時間為最佳排程(以總加權完工時間為目標)完工
時間之上限值。進而利用這個特性，提出一分解演算法，將可分解的問題
加以分解成數個子問題。此外，我們提出一優勢部份排序，證明在分枝界
限法中，若一節點能找到一優勢部份排序，則可以將此節點刪除；接著，
我們探討如何針對一節點，利用一啟發式方法找出其可能之優勢部份排序
，並將其應用在分枝界限法中，藉以進一步刪除多餘的節點，加快解題速
度。實驗結果顯示，當工件的到達時間較鬆散時，使用分解演算法確實能
節省許多解題的時間。另外，實驗亦證實了，將優勢部份排序應用在分枝
界限法中時，確實能有效地刪除不必要的節點，減少解題所需的時間。

關鍵字

單機排程 ； 分枝界限法

並列摘要

This research addresses a single machine scheduling problem
with unequal release date to minimize the total weighted
comple- tion time. The objective of minimizing the total
weighted com- pletion time is equivalent to that of minimizing
the WIP cost and different weights of job stand as different
value of jobs. This problem was proved to be NP-Complete. We
find that under certain conditions the problem can be de-
composed into several sub-problems with smaller problem sizes.
We also prove that the makespan of the WSPT sequence is
greater than or equal to that of the optimal sequence for any
job sets. Thus, a decomposition algorithm for this problem
isdeveloped according to this property. Finally, a dominant
partial sequence property is provided by this research. By
applying a heuristic algorithm to each node generated by the
branch and bound proce- dure, a dominant partial sequence of
current node can be found. If the heuristic algorithm finds a
dominant partial sequence, then the current node can be
eliminated. Experimental results show the computation times are
reduced when the release dates of jobs are loose and the
decomposition algorithm is applied. On the other hand, it was
concluded that the property of dominant partial sequence surely
eliminates un- necessary nodes effectively and efficiently in a
branch and bound procedure.

並列關鍵字

Single Machine Scheduling ； Branch and Bound