Abstract
背景介紹
The job-shop scheduling problem is well known for its complexity as an NP-hard problem. We have considered JSSPs with an objective of minimizing makespan while satisfying a number of hard constraints.
作為NP難問題梆造，作業(yè)車間調(diào)度問題以其復(fù)雜性而眾所周知。 我們已經(jīng)考慮了JSSP葬毫，其目標(biāo)是在滿足許多硬約束的同時最小化完工時間镇辉。
方法
In this paper, we developed a memetic algorithm (MA) for solving JSSPs. Three priority rules were designed, namely partial re-ordering, gap reduction and restricted swapping, and used as local search techniques in our MA.
在本文中，我們開發(fā)了一種用于求解JSSP的模因算法（MA）贴捡。 設(shè)計了三個優(yōu)先級規(guī)則忽肛，即部分重新排序，間隙減少和限制交換烂斋，并在我們的MA中用作本地搜索技術(shù)屹逛。
實驗結(jié)果
We have solved 40 benchmark problems and compared the results obtained with a number of established algorithms in the literature. The experimental results show that MA, as compared to GA, not only improves the quality of solutions but also reduces the overall computational time.
我們已經(jīng)解決了40個基準(zhǔn)問題，并將所獲得的結(jié)果與文獻(xiàn)中的許多已建立的算法進(jìn)行了比較汛骂。 實驗結(jié)果表明罕模，與GA相比，MA不僅提高了解決方案的質(zhì)量帘瞭，而且縮短了整體計算時間淑掌。
Conclution
Although JSSP is a very old and popular problem, still no algorithm can assure the optimal solution for all test problems, specifically for larger problems appearing in the literature. However, GAs and MAs are gaining popularity due to their effectiveness of solving optimization problems within a reasonable time period. In this paper, we have presented genetic and memetic algorithm based approaches to solve job-shop scheduling problems. After developing a traditional GA with different kind of operations, we have designed and implemented three local searches and three versions of memetic algorithms. All three memetic algorithms provided superior results than the GA for JSSPs.?
雖然JSSP是一個非常古老和流行的問題，但仍然沒有算法可以確保所有測試問題的最佳解決方案蝶念，特別是對于文獻(xiàn)中出現(xiàn)的較大問題抛腕。然而，由于GA和MA在合理的時間段內(nèi)解決優(yōu)化問題的有效性祸轮，因此越來越受歡迎兽埃。在本文中，我們提出了基于遺傳和模因算法的方法來解決作業(yè)車間調(diào)度問題适袜。在開發(fā)了具有不同類型操作的傳統(tǒng)GA之后柄错，我們設(shè)計并實現(xiàn)了三個本地搜索和三個版本的模因算法。對于JSSP，所有三種模因算法都比GA提供了更好的結(jié)果售貌。
We have solved 40 benchmark problems and have compared results with well-known algorithms appearing in the literature. Our?memetic algorithm MA(GR-RS) clearly outperforms all the algorithms considered in this paper.We have also provided a sensitivity analysis of parameters and have also experimented with different parameters and algorithms for analyzing their?contributions.Although our algorithm is performingwell, we feel that the algorithm requires further work to ensure consistent performance for a wide range of practical JSSPs. We intend to extend our research by introducing constraints such as, machine breakdown, dynamic job arrival, machine addition and removal, and due date restrictions. Moreover, we would also like to test the performance of our algorithm on large scale problems. However, the new memetic algorithm is a significant contribution to the research of solving JSSPs.
我們已經(jīng)解決了40個基準(zhǔn)問題给猾，并將結(jié)果與??文獻(xiàn)中出現(xiàn)的眾所周知的算法進(jìn)行了比較。我們的模因算法MA（GR-RS）明顯優(yōu)于本文考慮的所有算法颂跨。我們還提供了參數(shù)的靈敏度分析敢伸，并且還嘗試了不同的參數(shù)和算法來分析它們的貢獻(xiàn)。雖然我們的算法表現(xiàn)良好恒削，但我們感覺該算法需要進(jìn)一步的工作池颈，以確保廣泛的實用JSSP的一致性能。我們打算通過引入約束來擴(kuò)展我們的研究钓丰，例如機器故障躯砰，動態(tài)作業(yè)到達(dá)，機器添加和移除以及到期日限制携丁。此外琢歇，我們還想測試我們的算法在大規(guī)模問題上的性能。然而梦鉴，新的模因算法對解決JSSP的研究做出了重要貢獻(xiàn)李茫。
