單機排程求最小遲誤之「兩比算法式」及其在軍事生產作業上之通用範疇

The Paired Comparison Algorithm for Min. Total Tardiness

田長模(Chang-Mo Tien) ； 劉基全(Ji-Chyuan Liou)

《國防管理學報》 9卷2期 (1988/06) Pp. 1-16

https://doi.org/10.29496/JNDM.198806.0001

摘要

本文介紹一種簡易的單機排程求最小遲誤模式：「兩比算法式」。這項筆者五六年前設計並引用於教學的探索式模式（Heuristic Model），只要先把待排的工作按SPT或EDD分別先作兩次排序，在所得排序單中，如果某兩項工作的前置後續關係，順序中都一致，即可確定在遲誤最小的序列中，這兩項作業的相關位置，也可進而決定最小遲誤排程中可能列入第幾位的工作有那些。當然如例證中的作業時間及交貨期二者完全不相關，則在此二種不同的序列中有可能所有工作的先後順序都不相同，因而不可能由此步驟，得到任何進一步的結論。但是，實務上，交貨期當然要視施工長短來決定，因之這種數學上假想的情況，在合理的生產事業中是不會出現的。先用SPT及EDD排上列各工作，因而大致決定單機作業中第一，第二每一排序位置，各有那些工作有排入的可能。次一步就可以自最先施工的第一排序位置開始，由前而後，順序就每一位置中可能入選的各工作，用兩比方式逐一比對以選擇一最合適的工作列入。兩比時也只要引用Baker一書第31頁所舉的簡單原則就足用了。實驗證明計算時間只有使用動態規劃法的1/16弱，已可以現場連線操作方式由現場生管人員操作引用，即時作排成修正。

關鍵字

最早交期 ； 最短作業時間 ； 已排工作總時間 ； 總遲誤 ； 兩比算法式

並列摘要

If a similar precedence relation exists for pair of jobs be arranged either in an EDD or a SPT sequence, to keep these jobs in this proper sequence would be able to min. the total tardiness of a production schedule.Based upon the above principle, a heuristic model for the Min. Total Tardiness Problem is presented in this paper. Actual computer time required to handle an eight jobs problem is less than 1/20 of a second. Attached Pascal program could be utilized in-practical shop scheduling operations.

並列關鍵字

EDD(Earliest Due Date) ； SPT(Shortest Processing Time) ； TS(The Time Where Unscheduled Job Could Be Scheduled) ； Total Tardiness ； Paired Comparison Algorithm