雙機流程型工廠在有機台限制下最小化最大延遲時間之研究

Minimizing maximum lateness in a two-machine flowhop with machine eligibility

王彥棋(Yen-Chi Wang)

指導教授 ： 蘇玲慧

中原大學/工學院/工業工程研究所/碩士(2007年)

https://doi.org/10.6840/cycu200700579

摘要

本研究將針對雙機流程型工廠在有機台限制下的問題加以探討，以最小化最大延遲時間為目標，提出分枝界線演算法與啟發式演算法。啟發式演算法結合了Johnson’s algorithm 以及 EDD rule 以由後往前排的形式呈現。並以worst-case analysis 來分析啟發式演算法的績效。

關鍵字

雙機流程型機台 ； 分枝界線法 ； 延遲時間 ； 最壞情況分析

並列摘要

The two-machine flowshop problem is considered in which at most one operation in machine 2. Each job must be processed without preemption firstly on machine 1 and then on machine 2. The objective is to minimize the maximum lateness. The problem is NP-hard. Both the heuristic and the branch and bound algorithms are established to solve the problem. The heuristic combined the Johnson’s algorithm (1954) with the EDD rule and sequence jobs from the last position toward the first position. A worst-case analysis is used to analyze the performance of the heuristic.

並列關鍵字

worst-case analysis ； Two-machine flowshop ； lateness ； branch and bound

參考文獻

[1] Allahverdi Ali, Aldowaisan Tariq. (2004). No-wait flowshop with bicriteria of makespan and maximum lateness. European Journal of Operational Research. 152 132-147.

[2] Baker, K. R. and Su Zaw-Sing. (1974). Sequencing with due-dates and early start times to minimize maximum tardiness. Naval Res. Logist. Quart. 21 171-176.

[3] Bertrand, M.T. Lin. (2001). Scheduling in the two-machine flowshop with due date constraints. International Journal of Production Economics. 70 117-123.

[4] Bratley, P., Florian, M. and Robillard, P.. (1973). On sequencing with earliest starts and due-date with application to computing bounds for the problem. Naval Res. Logist. Quart. 20 57-67.

[5] Garey, M. R., Graham, R. L. and Johnson, D. S. (1978). Performance guarantees for scheduling algorithms. Operations Research. 26 3-21.