考慮多重加工之最小化最大提早和延遲時間之單機排程問題

Scheduling multi-operation jobs for minimizing the sum of maximum earliness and tardiness on a single machine

李睿杰(Ruei-Jie Li)

指導教授 ： 蘇玲慧

中原大學/電機資訊學院/工業與系統工程研究所/碩士(2009年)

https://doi.org/10.6840/cycu200901246

摘要

本研究擬針對靜態單機排程環境下考慮多重加工之最小化最大提早和延遲時間問題做研究，並且發展一啟發式演算法與一下限值。本研究針對啟發式演算法之求解時間與比較啟發式演算法與下限值之求解差距來做討論，研究中之基礎理論與優先順序關係將由相關文獻中衍生推演提出。此啟發式演算法將把family以批次的方式排放到機台中，並將已知完工時間的operation在family內做適當的排序，藉此能夠使目標值能夠達到最小化。啟發式演算法與下限值都將實驗測試，其過程與實驗結果將會在研究中詳細說明。

關鍵字

單機 ； 多重加工 ； 延遲時間 ； 提早時間

並列摘要

We consider the single machine multi-operation jobs scheduling problem. Each job
consists of several operations that belong to different families. In a schedule, each
family of job operations may be processed in batches. A job completes when all of its
operations have been processed. Our analysis criteria: minimizing the sum of
maximum earliness and tardiness. In the literature, we develop a heuristic algorithm
about minimizing the sum of maximum earliness and tardiness problem. The exact approach are tested and detailed computational results are given and we also propose a heuristic algorithms and their results are reported.

並列關鍵字

tardiness ； single machine ； multi-operation ； earliness

參考文獻

[1]Baker, K.R. and Magazine, M.J., 2000, Minimizing maximum lateness with job families, European Journal of Operational Research, 127, 126-139.

[2] Cheng, T.C.E., Ng, C.T. and Yuan, J.J., 2002, Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem, Imformation Processing Letters, 82, 187-191.

[4]Cheng, T.C.E., Ng, C.T. and Yuan, J.J., 2007, Single machine scheduling of multi-operation jobs without missing operations to minimize the total completion time, European Journal of Operational Research, 191, 320-331.

[6]Li, G.., 1997, Single machine earliness and tardiness scheduling, European Journal of Operational Research, 96, 546-558.

[7]Sidney, J., 1977, Optimal single-machine scheduling with earliness and tardiness penalties, Operations Research, 25, 62-69.