離散型回溯搜索最佳化演算法求解隨機性零工式生產排程問題

A Discrete Backtracking Search Optimization Algorithm for Solving Stochastic Job Shop Scheduling Problem

陳政擁(JENG-YUNG CHEN)

指導教授 ： 洪士程

朝陽科技大學/資訊學院/資訊工程系/碩士(2016年)

摘要

本篇碩士論文針對隨機性零工式生產排程問題(SJSSP)提出一個離散型回溯搜索最佳化演算法(DBSA)，利用回溯搜索最佳化演算法(BSA)多點平行搜尋的有效率性，搭配最佳資源預算分配(OCBA)快速且有效率篩選候選解，其目標是在有限的計算時間內有效地求出一個具有高可靠性且足夠好的排程解。SJSSP是非常實際且經常被討論的生產排程問題，其隨機性是指工件在機台上所需之加工時間透過某種機率分配，這個問題已經被確認為一個非確定性多項式時間內得出具有判定性解(NP-hard)的問題。為解決此複雜問題，我們將此實際問題轉換成一個具有限制條件的隨機模擬最佳化問題，並以最小化延遲(Tardiness)處罰和庫存(Earliness)處罰的總和為績效指標，當作是目標函數。選定的二個測試範例，包含具有6個工件與6個機台以及具有 10個工件與10個機台，針對三種不同的加工時間機率分布:結尾常態、均勻、指數函數分別進行實驗。最後將DBSA與基因演算法(GA)、瀰集演算法(MA)以及常用的派工法則進行比較，結果顯示所提出的DBSA可在有限的計算時間內得到一個足夠好的排程解。

關鍵字

隨機性零工式生產排程問題 ； 離散型回溯搜索最佳化演算法 ； 最佳資源預算分配 ； 延遲 ； 庫存

並列摘要

This thesis proposes a discrete backtracking search optimization algorithm (DBSA) to solve the stochastic job shop scheduling problem (SJSSP). The proposed DBSA utilizes the advantage of multi-directional search in backtracking search optimization algorithm (BSA) and quickly and efficiently selecting candidate solution in optimal computing budget allocation (OCBA). The goal is to find a good enough and high reliable solution in a reasonable computation time. The SJSSP is a practical and popular job shop scheduling problem. The stochastic characteristic indicates that the process time of a job is fluctuant randomly. The SJSSP is an NP-hard problem. To solve this NP-hard problem efficiently, the SJSSP is first formulated as a constraint stochastic simulation optimization problem with the objective function considering the sum of tardiness and earliness. Two examples include 6 jobs on 6 machines and 10 jobs on 10 machines are used to test the proposed DBSA. The random processing time in the experiment has three distributions: truncated normal, uniform, and exponential. The proposed DBSA is compared with Genetic algorithm, memetic algorithm, and existing dispatching rules. Result shows that the proposed DBSA can obtain a good enough solution in a reasonable computation time.

並列關鍵字

Stochastic job shop scheduling problems ； Discrete backtracking search optimization algorithm ； Optimal computing budget allocation ； Tardiness ； Rarliness

參考文獻

[3] D.M. Lei and H.J. Xiong, "An efficient evolutionary algorithm for multi-objective stochastic job shop scheduling," in Proc. Of Sixth International Conference on Machine Learning Cybernetics, Hong Kong, pp. 867-872, 2007.

[4] B.D. Parrello, W.C. Kabat and L. Wos, "Job-shop scheduling using automated reasoning: A case study of the car-sequencing problem," Journal of Automated Reasoning, 1986, Vol. 2, Issue 1, pp. 1-42

[5] M. Pinedo, "Stochastic scheduling with release dates and due dates," Operations Research, Vol.31, pp. 559-572, 1983.

[6] R.R. Weber, P. Varaiya, J. Walrand, "Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flow time," Journal of Applied probability, Vol. 23, pp. 841-847, 1986.

[7] C. Rajendran and O. Holthaus, "A comparative study of dispatching rules in dynamic flow shops and job shops," European Journal of Operational Research, Vol. 116, pp. 156-170, 1999.