最大延遲時間限制下以完成時間最小絕對偏差為準則之單機排程問題

本研究要探討的是單機排程中有最大延遲時間限制之最小化平均絕對偏差(Mean absolute deviation, MAD)的排程問題，每個工作擁有相同的到期時間窗。為了方便探討最大可容許延遲時間(maximum tardiness)限制對本問題的影響，假設到期時窗位於未來距離目前很遙遠的時間點(large common due date)，使得整個排程不需要從時間零開始加工。完成時間最小絕對偏差的問題從過去文獻可以知道工作都是呈現V形(V-shape)排列，本研究推論出有最大延遲時間的限制下也同樣擁有V形的特性。另外此問題中最大可容許延遲時間的大小可將此問題分成三種類別，分別是不受限的最大延遲時間(△-unconstrained)、受限制的最大延遲時間(△-constrained)以及嚴格受限制的最大延遲時間(tightly △-constrained)。本研究中計劃提出一些基礎定理和優勢凌越關係的特性，使得最佳化分支界限演算法能利用這些定理和優勢凌越關係以及V形排列特性更有效率的求解出最佳解。由於分支界限法過程中每一節點只要分支兩邊，用以決定該工作將提早或延遲完成，因此能提升分支界限演算法的求解效率。另外發展出啟發式演算法用以處理工作數較大的問題，並將會透過實驗測試其求解品質及效率。

關鍵字

最小絕對偏差時間；單機排程；最大延遲時間；到期時間窗

並列摘要

This research deals with the problem of scheduling a number of jobs on a single machine to minimize mean absolute deviation of job completion time about a common due window with maximum tardiness constraint (MAD/ problem). When constraint is imposed, the common due window is set to be large to allow the idle time prior to starting the first job in order to examine the effect of the constraint. It is assumed that no penalties will occur if a job is completed within the due window. However, the penalties will occur if a job is completed outside the due window. When constraint is considered for the MAD problem, we found the schedule is still V-shaped. The problem is classified into three cases according to the value of maximum allowable tardiness: △-unconstrained, △-constrained and tightly △-constrained cases. Some solution properties and dominance relationships will be proposed to expedite the solution algorithm. The exact algorithm of Branch-and-Bound algorithm will be developed based on these solution properties. Besides, in order to deal with the problems with large number of jobs, the heuristic algorithm will be developed.

並列關鍵字

maximum tardiness ； MAD ； single machine schedule ； common due window

參考文獻

[1] Alidaee, B., Dragan, I., A note on minimizing the weighted sum of tardy and early completion penalties in a single machine: A case of small common due date, European Journal of Operational Research 96(1997) 559-563.

[2] Azizoglu, M., Webster, S., Scheduling about an unrestricted common due window with arbitrary earliness/tardiness penalty rates, IIE Transactions 29(1997) 1001-1006.

[3] Baker, K.R., Scudder, G.D., Sequence with Earliness and Tardiness Penalties, Operations Research 38 (1990) 22-36.

[4] Bagchi, U., Sullivan, R.S., Chang, Y.L., Minimizing Mean Absolute Deviation of Completion Times about a Common Due Date, Naval Research Logistics Quarterly 33(1986) 227-240.

[5] Bagchi, U., Sullivan, R.S., Chang, Y.L., Minimizing Mean Squared Deviation of Completion Time about a Common Due Date, Management Science 33 (1987) 894-906.

國際替代計量

最大延遲時間限制下以完成時間最小絕對偏差為準則之單機排程問題

未授權

主題瀏覽