利用線性規劃求解可變作業強度之專案排程問題

Solving Project Scheduling Problem with Variable Activity Intensity by Linear Programming

吳俊炘(Jun Wu)

指導教授 ： 洪一峯

國立清華大學/工學院/工業工程與工程管理學系/碩士(2007年)

https://doi.org/10.6843/NTHU.2007.00350

摘要

本研究主要探討可變作業強度(variable activity intensity)之資源限制專案排程問題(resource constrained project scheduling problem with variable activity intensity)。此問題之特性在於專案中之作業其資源耗用率為可變動的，當一個作業的資源耗用率愈高，其作業時間愈短，也愈快完成，資源耗用率與作業強度呈正比的關係。“作業強度”一詞乃由Hackman and Leachman【1989】根據Leontief生產函數理論所衍生。而Leachman et al.【1990】應用Leontief生產函數理論提出作業強度與作業時間呈倒數關係及作業強度與資源耗用率呈正比關係。因此，作業強度可建立作業時間及資源耗用率的關係並應用於資源限制專案排程問題。
近年該類範疇之研究文獻甚少，除了使用非線性規劃(nonlinear programming)或混整數規劃(mixed integer linear programming)表達問題之外，並未提供測試問題，因此無法得知文獻所提方法求解問題之效能。本研究主要利用線性規劃模式建構問題，並產生測試問題探究本方法求解結果與成效。
使用線性規劃遭遇的困難有二：第一，作業強度與作業時間呈非線性之凸函數(convex)關係，因此本研究將使用片段線性曲線(piece-wise linear curve)近似作業強度與作業時間呈非線性之凸函數關係；第二，專案有很多組可能事件順序，事件順序的不同會產生不同的資源限制式，本研究提出一個系統化的方法求解問題。首先建構一個計算方法搜尋專案所有可能的事件順序，有了片段線性曲線及一組事件順序即可建構一個線性規劃問題，比較所有事件順序所產生之線性規劃之目標值即可得出問題的近似最佳解。

關鍵字

資源限制專案排程 ； 可變作業強度 ； 線性規劃 ； 片段線性曲線

並列摘要

In this study, we consider a resource constrained project scheduling problem with variable activity intensity. In this problem, the resource consumption of an activity is a variable and is proportional to the activity intensity. Based on the theory of Leontief production functions, Hackman and Leachman 【1989】 first introduce the concept of activity intensity. Leachman et al.【1990】 apply the theory of Leontief production functions to project scheduling problem and propose that the resource consumption is proportional to activity intensity, and the activity duration is the reciprocal of the activity intensity. Therefore, the activity intensity can be used to establish the relationship between resource consumption and activity duration in a resource constrained project scheduling problem.
However, our literature survey reveals that only a few studies focused on this type of problem. These researchers used a nonlinear program or a mixed integer linear program to model the problem. If a heuristic approach is used, it cannot guarantee an optimal solution. Hence, we propose an approach that uses a linear program formulation.
To use linear program, we have to take care of two problems. The first problem is that the actual relationship between intensity and duration is nonlinear convex function. In this study, we propose to use piece-wise linear curve to approximate the nonlinear convex curve. The second problem is that there are many feasible event sequences. An event sequence unique determines a set of resource constraints of its corresponding linear programming problem. Therefore, by solving all the linear programs of all the feasible event sequence, we can obtain the optimal solution of the resource constrained projected scheduling problem.
Keywords: resource constrained project scheduling, variable intensity activities,linear programming, piece-wise linear curve

並列關鍵字

resource constrained project scheduling ； variable intensity activities ； linear programming ； piece-wise linear curve

參考文獻

Alvarez-Valdes, A. and Tamarit, J. M. (1989), “Heuristic algorithms for resource constrained project scheduling: a review and an empirical analysis.”, in: Slowinski, R. and Węglarz, J.(eds.), Advances in Project Scheduling, Elsevier, Amsterdam, pp.113-134.

Baroum, S. and Patterson, J. H. (1989), “A heuristic algorithm for maximizing the net present value of cash flows in resource constrained project schedule.”, Working Paper, Indiana University.

Bell, C. E. and Han, J. (1991), “A new heuristic solution method in resource constrained project scheduling problems.”, Naval Research Logistics, Vol. 38, pp. 315-331.

Bell, C. E. and Park, K. (1990), “Solving resource constrained project scheduling problems by A* search.”, Naval Research Logistics, Vol. 37, pp. 61-84.

Bock, D. B. and Patterson, J. H. (1990), “A comparison of due date setting, resource assignment and job preemption heuristics for the multiproject scheduling problem.”, Decision Sciences, Vol. 21, pp. 387-402.