Makespan Minimization on Iidentical Parallel Machines Subject to Minimum Total Flow-Time

最小總流程時間條件下針對平行機台總作業時間跨距最佳化研究

Jatinder N. D. Gupta ； Johnny C. Ho ； Alex J. Ruiz-Torres

《工業工程學刊》 21卷3期 (2004/05) Pp. 220-229

https://doi.org/10.29977/JCIIE.200405.0002

摘要

本研究探討n項工作在m個平行機台的排程問題，而求解問題所谓的最佳化排程定義爲在最佳化總流程時間（亦即所有工作作業時間之總和）下所有排程法則集合中最小化之總作業時間跨距（亦即任一平行機台中最後一項作業的完成時間）。本研究提出兩個創新且簡易的啓發式演算法並和既有的演算法進行經驗法則之效率和效度的比較。

關鍵字

平行機台排程 ； 啓發式凖則 ； 總時間跨距 ； 流程時間 ； 啓發式演算法 ； 經驗法則

並列摘要

We consider the problem of scheduling n jobs on m identical parallel machines. An optimal schedule to the proposed problem is defined as one that gives the smallest makespan (the completion time of the last job on any one of the parallel machines) among the set of all schedules with optimal total flow time (the sum of the completion times of all jobs). We propose two new simple heuristic algorithms and empirically compare their effectiveness and efficiency with several existing algorithms.

並列關鍵字

Parallel machine scheduling ； hierarchical criteria ； makespan ； flowtime ； heuristic algorithms ； empirical results

參考文獻

Bruno, J. L.,E. G. Coffman,R. Sethi(1974).Algorithms for minimizing mean flow time.IFIPS Congress 74.74,504-510.

Coffman, E. G.,R. Sethi(1976).Algorithms minimizing mean flow time: schedule length properties.Acta Informatica.6,1-14.

Coffman, E. G.,M. R. Garey,D. S. Johnson(1978).An application of bib-packing to multi-processor scheduling.SIAM Journal on Computing.7,1-17.

Conway, R. W.,W. L. Maxwell,L. W. Miller(1976).Theory of scheduling.MA:Addison Wesley.

Eck, B. T.,M. Pinedo(1993).On the minimization of the makespan subject to flowtime optimality.Operations Research.41,797-801.