Deterioration Function Yielding an Index Rule

以指標法則對惡化作業之排程方法研究

Ali Derbala

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

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

摘要

本研究考慮一平均限制優序排程法則稱之爲MBPS，藉由對每一工作進行指標計算作業時間比率與等候時間比率，對兩者之權重加總作爲優序化依據。本研究證明MBPS排程法則可以有效求解惡化作業或是單一機台延誤作業之排程問題。此動態優序化問題可以藉由以下兩種方式表達：一爲藉由計算工作之作業時間減少量；二爲藉由計算個別故障機台之待機或是維修時間等方式表達。而本研究可以具體驗證排程方式之特性可以透過以上兩種成果加以建構。最後，MBPS排程法則可以依據指標排程策略來有效求解惡化作業之排程問題。

關鍵字

異質批次處理器 ； 不相容工作族 ； 啓發式演算法 ； 敏感度分析

並列摘要

We consider a scheduling rule called MBPS, the mean bounded priority scheduling, which prioritizes jobs by an index computed for each job as a weighed sum of the proportion of time it has been processed and the proportion of time it has been waiting for processing. Proof that MBPS is a deteriorating or a delaying jobs single-machine scheduling problems is given. Two expressions of this dynamic priority are interpreted as a net-reduction in the processing of a job and a delay caused or a time to repair a breakdown respectively. As to the behavior of this scheduling scheme, two results are established. MBPS is shown to be a deterioration function yielding an index policy.

並列關鍵字

deteriorating job ； delaying job ； index rule ； stochastic scheduling and MBPS

參考文獻

Browne, S.,U. Yechiali(1990).Scheduling deteriorating jobs on a single processor.Operations Research.38(3),495-498.

Cai, J. Y.,P. Cai.,Y. Zhu(2003).To appear in Journal of Complexity.

Gittins, J. C(1979).Bandit process and dynamic allocation indices.Journal of Royal statistics society B.41(2),148-177.

Gittins, J. C.(1989).Multi-armed Bandit allocation indices.New York:John Wiley and sons.

Gittins, J. C.,K. D. Glazebrook(1977).On Bayesian models in stochastic scheduling.Journal of applied probability.14,556-565.