平行機製程在資源限制下之排程問題

Scheduling parallel machines with resource flexibility

練俊源(Chun-Yuan Lien)

指導教授 ： 蘇玲慧

中原大學/工學院/工業工程研究所/碩士(2003年)

https://doi.org/10.6840/cycu200300629

摘要

摘要
本研究旨在探討平行機製程在資源限制下之排程問題，每一工作的作業時間為分配給此工作使用之資源量的線性遞減函數，但系統須受限於總資源量的限制，其目標為求得工作的排程與資源的配置使得總完成時間(Makespan)最小。等效平行機問題之複雜度早已被證明為NP-hard，再加上資源使用之考量將使問題更加繁複，因此本研究分別針對平行機與資源的配置發展求解方法，並提出兩個啟發式演算法，最後發展一個全域下限值，以驗證演算法的求解品質與效率。經實驗證明本研究所發展的求解工作排程之演算法不論在求解品質或求解時間上均具有極佳的績效；兩個啟發式演算法也有極佳的表現，其總平均求解品質分別達98.31%與99.65%。

關鍵字

全域下限值 ； 線性遞減函數 ； 平行機 ； 資源限制

並列摘要

Abstract
We consider the problem of scheduling a set of jobs on parallel machines where the processing time of a job may be reduced linearly by the application of a limited discrete resource. The objective is to determine the job assignment to machines and the allocation of resources to jobs so that the makespan is minimized. This problem is a combination of parallel machines problem and the time/cost trade-off problem. Two versions of the problem are introduced. One identifies the job sequence first and then the resource distribution while the other consider the resource distribution first and then the job sequence. A resource based global lower bound is presented for benchmarking. Experimental results show that the heuristic algorithm proposed in the paper for P||Cmax problem is superior to LISTFIT algorithm, and both heuristics proposed for the whole problem have outstanding performances.

並列關鍵字

linear reduction ； resource constraint ； parallel machines ； global lower bound

參考文獻

1. Ahn, T. and Erenguc, S.S., 1998, The resource constrained project scheduling problem with multiple crashable modes, European Journal of Operational Research, 107, 250-259.

2. Alidaee, B. and Ahmadian, A., 1993, Two parallel machine sequencing problems involving controllable job processing times, European Journal of Operational Research, 70, 335-341.

3. Berman, E.B., 1964, Resource allocation in a PERT network under continuous activity time cost functions, Management Science, 10, 734-745.

4. Boctor, F.F., 1996, A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes, European Journal of Operational research, 90, 349-361.

5. Brucker, P., Knust, S., Schoo, A. and Thiele, O., 1998, A branch and bound algorithm for the resource-constrained project scheduling problem, European Journal of Operational research, 107, 272-288.