工作可分割之平行機台排程

Parallel Machine Scheduling with Job Splitting

葉士綸(Shih-Lun Yeh)

指導教授 ： 洪一峯

國立清華大學/工學院/工業工程與工程管理學系/碩士(2009年)

https://doi.org/10.6843/NTHU.2009.00227

摘要

本論文主要在探討當工作可分割時之等效平行機台排程問題。在本問題中，假設一個工作可以被分成許多的子工作，並且可將這些子工作指派到不同的機台上同時加工。每個工作具有已知的加工時間、準備時間以及交期。在機台加工過程中，當欲加工工作與前一加工工作不同時，必須耗費一相依整備時間方能進行加工。為最小化此問題之總延遲時間，本論文提出一個兩階段式方法來求解此問題。第一階段中，本論文提出五種初步排程產生方法。接著在第二階段中，將在第一階段產生的排程中有延遲的工作或子工作做進一步分割，並將分割後的子工作重新指派到機台上以減少總延遲時間。由實驗結果顯示，本論提出之方法表現優於前人所提出之方法。

關鍵字

排程 ； 平行機台 ； 工作可分割 ； 總延遲時間 ； 相依整備時間

並列摘要

This study focuses on the problem of scheduling jobs on identical parallel machines with job-splitting property. In this problem, it assumed that a job can be split into several sub-jobs, and these sub-jobs can be processed on different machines simultaneously. Each job has a processing time, a ready date and a due date. If a sub-job of a job is assigned after a sub-job of another job on a machine, a sequence-dependent setup time is incurred. A two-phase heuristic algorithm is proposed to minimize the total tardiness. In phase 1, five efficient heuristic methods are proposed. In phase 2, the sub-job of tardy jobs in the schedule provided by phase 1 are further split, and the split sub-jobs are rescheduled on the machines to reduce the total tardiness. Computer experiments show that the proposed algorithm outperforms a previously suggested algorithm.

並列關鍵字

Scheduling ； Parallel machines ； Job splitting ； Total tardiness ； Sequence dependent setup times

參考文獻

Chen, B., Ye, Y. Y. and Zhang, J. W. (2006), “Lot-sizing scheduling with batch setup times”, Journal of Scheduling, Vol. 9, No. 3, pp. 299-310

Lee, Y. H. and Pinedo, M. (1997), “Scheduling jobs on parallel machines with sequence-dependent setup times”, European Journal of Operational Research, Vol. 100, No. 3, pp. 464-474

Logendran, R. and Subur, F. (2003), “Unrelated parallel machine scheduling with job splitting”, IIE Transactions, Vol. 36, No. 4, pp. 359-372

Koulamas, C. (1994), “The total tardiness problem: Review and extensions”, Operations Research, Vol. 42, No. 6, pp. 1025-1041

Koulamas, C. (1997), “Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem”, Naval Research Logistics, Vol. 44, No. 1, pp. 109-125