運用仿電磁理論演算法求解單機排程問題

An application of electromagnetism-like mechanism for the single machine scheduling problem

陳冠翰(Kuan-Han Chen)

指導教授 ： 曾兆堂

朝陽科技大學/理工學院/工業工程與管理系/碩士(2010年)

摘要

本研究所要探討的問題為「單機階段式總延遲成本最小化」，在實務上當遇到有關延遲問題時，通常顧客都會給予多個到期日作為完工時間，如果超過到期日，會因為不同階段的到期日產生不同階段的懲罰成本。所以，本研究稱此準則為階段式延遲成本（Stepwise Tardiness Cost）。
本研究應用仿電磁理論演算法，求解階段式延遲成本準則的單機排程問題。在提出的仿電磁理論演算法中，首先，使用順序編碼方式來表示一個解。接著，應用類似基因演算法的機制，設計一個新的運算方式使其順利求解考慮的問題。
最後，本研究將提出的仿電磁理論演算法與其他不同演算法作比較。實驗結果顯示，在小工件數的情況下，可獲得良好的績效，且在大工件數的情況下也可得不錯的近似解。

關鍵字

排程 ； 單機 ； 階段式總延遲成本 ； 仿電磁理論演算法

並列摘要

This paper investigates a single machine scheduling problem with total stepwise tardiness criterion. In practice, customers usually provide several late periods. At the different late periods, firms would pay the different fixed tardiness cost. In this study, the new criterion of scheduling is called stepwise tardiness cost.
This paper applies an electromagnetism-like mechanism (EM) to minimizing the total stepwise tardiness cost in a single machine. In the proposed EM algorithm, first, we use an encoding scheme of a processing sequence as a particle. A new operator of EM algorithm, based on the mechanism of genetic algorithm, is designed to successfully implement on EM algorithm.
Finally, this paper will compare the proposed EM algorithm with other meta-heuristics. The experimental results show that the proposed EM algorithm obtains a good performance for the small-sized problems, and a good approximate solution for the large-sized problems.

並列關鍵字

Single machine ； Total stepwise tardiness ； Electromagnetism-like mechanism ； Scheduling

參考文獻

周盈君，「變動鄰域搜尋法求解單機階段式延遲問題」，碩士論文，朝陽科技大學工業工程與管理研究所，台中(2009)。

Chang, P. C., Chen, S. H. and Fan, C.Y., “A Hybrid Electromagnetism-Like Algorithm For Single Machine Scheduling Problem,” Expert Systems with Applications, 36, 1259–1267, (2009).

Cheng, T.C.E., Ng, C.T. and Yuan, J.J., “Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs,” Theoretical Computer Science, 362, 273–281, (2006).

Cheng, T.C.E., Ng, C.T., Yuan, J.J. and Liu, Z.H., “Single machine scheduling to minimize total weighted tardiness,” European Journal of Operational Research, 165, 423–443, (2005).

Congram, R.K., Potts, C.N. and Van De Velde, S.L., “An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem,” INFORMS Journal on Computing, 14, (1), 52–67, (2002).