等效平行機台在工件依批量到達下之最小總完工時間排程問題

Minimizing Total Flowtime with Arrival Time in Batches on Identical Parallel Machines

10.6840/CYCU.2007.00288、10.6840/cycu200700416

鍾翠萍

等效平行機台 ； 到達時間 ； 分支界限法 ； 最小總完工時間 ； arrival time ； identical parallel machines ； total flow-time ； branch and bound algorithm

中原大學工業工程研究所學位論文

2007年

碩士

蘇玲慧

繁體中文

本研究將針對等效平行機台在工件依批量到達情況下之排程問題加以探討，以最小總完工時間為目標。此問題已被證明為NP-hard問題，因此提出啟發式演算法並以分支界限法驗證。啟發式演算法先針對每一批量依SPT方法達到部分最佳化並利用BIP數學模式降低在每一個批量到達之間隔時間裡的空閒時間達到最小總完工時間之目標。實驗分成兩個部份由透過實驗測試得到啟發式演算法之求解品質誤差最多為6.7%。

This paper considers the identical parallel machines problem, where jobs arrive in batches. The objective is to minimize the total completion time. Since the single machine problem with job arrival time is known to be NP-hard, therefore the problem is NP-hard in the strong sense. A heuristic procedure based on a Binary Integer Programming model to level the completion time of all jobs between two consecutive batch arrival times is developed to decrease the machine idle, which in turn minimize the total job completion time. A branch and bound algorithm is proposed for benchmarking. Computational results show that the solution quality error of the heuristic is at most 6.7%.

1. [1] Azizoglu, M., Kirca, O., 1999. On the minimization of total weighted flow time with identical and uniform parallel machines. European journal of operational research 113, 91-100
   連結：
2. [2] Barnes, J.W.,Brennan, J.J., 1977.An improved algorithm for independent tasks to reduce mean finishing time. AIIE Transactions 17,382-387.
   連結：
3. [3] Belouadeh, H.,Potts, C.N., 1994.Scheduling identical parallel machines to minimize total weighted completion time.Discrete Applied Mathematics 48, 201-218.
   連結：
4. [4] Chu, C., 1992. A branch-and-bound algorithm to minimize total flow time with unequal release dates. Naval Research Logistics 39, 859-875.
   連結：
5. [6] Du, J., Leung, J.Y-T., Young, G.H., 1991. Scheduling chain-structured tasks to minimize makespan and mean flow time. Information and Computation 92, 219-236.
   連結：
6. [7] Elmaghraby, S.E., Park, S.H., 1974. Scheduling jobs on a number of identical machines. AIIE Transactions 6, 1-13.
   連結：
7. [8] Gupta, JND, Ho, J.C., Webster, S., 2000. Bicriteria optimization of the makespan and mean flowtime on two identical parallel machines. Journal of the Operational Research Society 51, 1330-1339.
   連結：
8. [9] Gupta, JND, Ho, J.C., 2001. Minimizing makespan subject to minimum flowtime on two identical parallel machines. Computers and Operations Research 28,705-717.
   連結：
9. [10] Gupta JND, Ruiz-Torres, A.J., 2000 Minimizing makespan subject to minimum total flowtime on identical parallel machines. European journal of operational research 125,370-380.
   連結：
10. [11] Ho, J.C., Wang, J.S., 1995. Makespan minimization for parallel identical processors. Naval Research Logistics 42,935-948.
    連結：
11. [12] Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P., 1977. Complexity of machine scheduling problems. Annals of Discrete Applied Mathematics 1,343-362.
    連結：
12. [13] Lin, C.H., Liao, C.H., 2004.Makespan minimization subject to flowtime optimality on identical parallel machines 31, 1655-1666.
    連結：
13. [15] Sarin, S.C., Ahn, S., Bishop, A.B., 1988. An improved branching scheme for the branch and bound procedure of scheduling jobs machines to minimize total weighted flow time. International Journal of Production Research 26, 1183-1191.
    連結：
14. [16] Yalaoui, F., Chu, C., 2006. New exact method to solve the schedule problem. International journal of production economics 100, 168-179.
    連結：
15. 參考文獻
16. [5] Conway, R.W., Maxwell, W.L.,Miller,L.W., 1967. Theory of Scheduling, Addison-Wesley, Reading, MA.
17. [14] Phillips, C.A., Schulz, A.S., Shmoys, D.B., Stein, C., Wein, J., 1998. Improved bounds on relaxation of a parallel machine scheduling problem. Journal of Combinatorial Optimization 1,413-426.