資源限制下之最小化加權完工時間總和

Abstract

本論文所探討的是在資源限制下最小化完工時間總和的排程問題，並將 重點聚焦於給定初始資源量的單一機台環境。在本類型的題目中，每個工作 會在執行前消耗並在結束後返還資源，而所消耗的資源量以及返還的資源量 並不一定相等。文獻中，此題目已知是屬於 NP-hard 的範疇。 在論文中，我們提出了兩種不同的整數規劃模型以描述此問題的全貌並 提供最佳解。同時，我們也提出了數種經驗法則演算法以求得不錯的近似 解，用來完善整數規劃於計算時間成長快速所面臨的不足之處。此外，本論 文亦設計了實驗來比較兩組整數規劃的效果以及分析經驗法則演算法所產生 的近似解之品質。

This study considers the minimization of total weighted completion time in a resource-constrained scheduling problem. A set of jobs is to be processed by a single machine with an initial level of resource provided for the jobs. Each job acquires and consumes an amount of the resource to start its processing, and will produce and return the resource. The amount of returned resource is not necessarily the same as that acquired. To minimize the total weighted completion time is known in the literature to be strongly NP-hard. In this thesis, two integer linear programming models are presented to formulate the problem and several heuristic algorithms are proposed to produce approximate solutions. A series of computational experiments are conducted in order to evaluate the performances of the proposed integer linear programming models and the three heuristic algorithms.