臺灣博碩士論文加值系統

在現實生產環境下普遍存在資源有限的情況，企業往往會為了如何運用現有資源或要如何使現有資源發揮最大效益而傷透腦筋，但大部分的排程研究都只將機器視為唯一資源，較少有同時考慮機器及其他資源限制之研究，例如同時考慮機器及能源限制或同時考慮機器及原物料限制等研究，而資源限制之排程問題在生產排程領域已被證明為NP-hard，若同時考慮雙資源或多資源限制將會增加問題研究之難度。
彈性流程式生產系統包含一個以上的工作站，每個工作站中至少要有一台以上的機器，每個工作經過工作站的順序是相同的，每個工作進入工作站中可任選一台機器進行加工，彈性流程式生產系統被運用在許多產業中，例如紡織、鋼鐵、裝配及製藥等產業，但過往文獻中關於在彈性流程式生產系統下考慮資源限制的研究並不多。
因此本研究針對在彈性流程式生產系統下考慮雙資源限制問題進行研究，並設定18種不同規模之資料進行測試，每個工作會在各個工作站中任選一台機器進行處理，在最後一個工作站中固定只有兩台機器，分別具有不同的資源限制，每個工作會根據其所需資源在最後一個工作站中進入擁有所需資源的機器進行處理，並透過改良式基因演算法求解最小化最大完工時間，最後比較改良式基因演算法與基因演算法求解的有效性以及穩定度。
測試結果顯示利用改良式基因演算法求解最小化最大完工時間，改良式基因演算法的改善率為6.20%，基因演算法的改善率為5.93%，在穩定度部分改良式基因演算法完工時間的標準差皆小於基因演算法之標準差，表示在求解雙資源限制之彈性流程式排程問題時改良式基因演算法之效能及穩定度皆高於基因演算法。

In the actual production environment, there are generally limited resources. Enterprises often brainstorm how to use existing resources or how to maximize existing resources. However, most scheduling studies only regard machines as the only resources. There are few studies that consider both machine and other resource restrictions, such as considering machine and energy restrictions or machine and raw material restrictions at the same time, and resource restriction scheduling has been proven to be NP-hard in the field of production scheduling If considering dual resource or multiple resource restrictions at the same time, it will increase the difficulty of problem research.
The flexible flow shop system contains more than one workstation, and each workstation must have at least one machine. The order of each work passing through the workstation is the same. Each machine can be selected for processing in the workstation.　Flexible flow shop systems are used in many industries, such as　textile, steel, assembly, and pharmaceutical industries. However, there are not many studies in the literature on resource constraints under flexible flow shop systems.
Therefore, this study focuses on the consideration of the problem of dual resource constraints in the flexible flow shop system, and sets 18 different scales of data for testing. Each job will be selected in each workstation for processing and the last workstation there are only two machines. The two machines have different resource constraints. Each job will be processed in the machine with the required resources in the last workstation according to its required resources. Solve the problem by minimizing the maximum completion time through the Modified genetic algorithms and compare the effectiveness and stability of the Modified genetic algorithms and the genetic algorithms.
The test results show that the Modified genetic algorithms is used to solve the problem of minimizing the maximum completion time. The improvement rate of the Modified genetic algorithms is 6.20%, and the improvement rate of the genetic algorithms is 5.93%. The standard deviations are all smaller than the standard deviations of the genetic algorithm, which means that the performance and stability of the improved genetic algorithm are higher than the genetic algorithm when solving the flexible flow shop scheduling with dual resource constraint.

目 錄
第壹章 緒論 1
第一節 問題背景與研究動機 1
第二節 研究目的 2
第三節 研究範圍與限制 3
第四節 研究流程 4
第貳章 文獻探討 6
第一節 彈性流程式生產排程問題 6
第二節 資源限制之排程問題 9
第三節 探索式演算法 11
第參章 研究方法 18
第一節 問題描述 18
第二節 數學模型建構 20
第三節 求解程序 24
第四節 釋例 27
第肆章 資料測試與分析 33
第一節 模擬資料與測試環境建立 33
第二節 模擬資料測試 35
第三節 測試結果彙整 40
第伍章 結論與建議 41
第一節 結論 41
第二節 建議與未來研究方向 43
參考文獻 44

表目錄
表 2-3-1 符號編碼示意表 14
表 3-4-1 釋例資料表 27
表 3-4-2 基因編碼表 28
表 3-4-3 最佳解工作排序表 31
表 4-1-1 問題規模彙總表 34
表 4-1-2 演算法之參數設定表 34
表 4-2-1 有效性測試結果 36
表 4-2-2 穩定性測試結果 39
表 4-3-1 測試結果彙整表 40

圖目錄
圖 1-4-1 研究流程圖 5
圖 2-3-1 基因演算法程序圖 13
圖 3-1-1 雙資源限制之彈性流程式生產系統示意圖 19
圖 3-3-1 求解程序圖 24
圖 3-4-1 基因編碼之甘特圖 29
圖 3-4-2 最佳解排序之甘特圖 31
圖 4-2-1 改善率曲線圖 37
圖 4-2-2 運算時間曲線圖 37

1.Araujo, J. A., Santos, H. G., Gendron, B., Jena, S. D., Brito, S. S., & Souza, D. S. (2020). Strong bounds for resource constrained project scheduling: Preprocessing and cutting planes. Computers & Operations Research, 113, 104782.
2.Behnamian, J., & Ghomi, S. F. (2011). Hybrid flow shop scheduling with machine and resource-dependent processing times. Applied Mathematical Modelling, 35(3), 1107-1123.
3.Benda, F., Braune, R., Doerner, K. F., & Hartl, R. F. (2019). A machine learning approach for flow shop scheduling problems with alternative resources, sequence-dependent setup times, and blocking. OR Spectrum, 41(4), 871-893.
4.Dai, M., Tang, D., Giret, A., Salido, M. A., & Li, W. D. (2013). Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robotics and Computer-Integrated Manufacturing, 29(5), 418-429.
5.Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on evolutionary computation, 1(1), 53-66.
6.Huang, R. H., & Yu, S. C. (2016). Two-stage multiprocessor flow shop scheduling with deteriorating maintenance in cleaner production. Journal of Cleaner Production, 135, 276-283.
7.Huang, R. H., Yu, S. C., & Chen, P. H. (2017). Energy-Saving Scheduling in a Flexible Flow Shop Using a Hybrid Genetic Algorithm. Journal of Environmental Protection, 8(10), 1037-1056.
8.Laribi, I., Yalaoui, F., Belkaid, F., & Sari, Z. (2016). Heuristics for solving flow shop scheduling problem under resources constraints. IFAC-PapersOnLine, 49(12), 1478-1483.
9.Liu, X., Wang, L., Kong, L., Li, F., & Li, J. (2019). A hybrid genetic algorithm for minimizing energy consumption in flow shops considering ultra-low idle state. Procedia CIRP, 80, 192-196.
10.Meng, L., Zhang, C., Zhang, B., & Ren, Y. (2019). Mathematical modeling and optimization of energy-conscious flexible job shop scheduling problem with worker flexibility. IEEE Access, 7, 68043-68059.
11.Nabli, Z., Khalfallah, S., & Korbaa, O. (2018). A two-stage hybrid flow shop problem with dedicated machine and release date. Procedia Computer Science, 126, 214-223.
12.Naderi, B., Gohari, S., & Yazdani, M. (2014). Hybrid flexible flowshop problems: Models and solution methods. Applied Mathematical Modelling, 38(24), 5767-5780.
13.Rooeinfar, R., Raissi, S., & Ghezavati, V. R. (2019). Stochastic flexible flow shop scheduling problem with limited buffers and fixed interval preventive maintenance: a hybrid approach of simulation and metaheuristic algorithms. Simulation, 95(6), 509-528.
14.Sehrawat, M., & Singh, S. (2011). Modified Order Crossover (OX) Operator. International Journal on Computer Science and Engineering, 3(5), 2019-2023.
15.Singh, A. (2014). Resource Constrained Multi-Project Scheduling with Priority
Rules & Analytic Hierarchy Process. Procedia Engineering, 69, 725-734.
16.Wang, H., Fu, Y., Huang, M., Huang, G. Q., & Wang, J. (2017). A NSGA-II based memetic algorithm for multiobjective parallel flowshop scheduling problem. Computers and Industrial Engineering, 113, 185-194.
17.Xu, W. J., He, L. J., & Zhu, G. Y. (2019). Many-objective flow shop scheduling optimisation with genetic algorithm based on fuzzy sets. International Journal of Production Research, 1-25.
18.Yu, A. J., & Seif, J. (2016). Minimizing tardiness and maintenance costs in flow shop scheduling by a lower-bound-based GA. Computers & Industrial Engineering, 97, 26-40.
19.Yu, C., Semeraro, Q., & Matta, A. (2018). A genetic algorithm for the hybrid flow shop scheduling with unrelated machines and machine eligibility. Computers & Operations Research, 100, 211-229.
20.Zarei, H., & Rasti-Barzoki, M. (2019). Mathematical programming and three metaheuristic algorithms for a bi-objective supply chain scheduling problem. Neural Computing and Applications, 31(12), 9073-9093.
21.Zhang, J., Wang, W., & Xu, X. (2017). A hybrid discrete particle swarm optimization for dual-resource constrained job shop scheduling with resource flexibility. Journal of intelligent Manufacturing, 28(8), 1961-1972.
22.Zhang, M., Yan, J., Zhang, Y., & Yan, S. (2019). Optimization for energy-efficient flexible flow shop scheduling under time of use electricity tariffs. Procedia CIRP, 80, 251-256.
23.Zhang, P., Bard, J. F., Morrice, D. J., & Koenig, K. M. (2019). Extended open shop scheduling with resource constraints: Appointment scheduling for
integrated practice units. IISE Transactions, 51(10), 1037-1060.
24.Zhang, W., Wen, J. B., Zhu, Y. C., & Hu, Y. (2017). Multi-objective scheduling simulation of flexible job-shop based on multi-population genetic algorithm. International Journal of Simulation Modelling, 16(2), 313-321.
25.Zhong, Q., Yang, H., & Tang, T. (2018). Optimization algorithm simulation for dual-resource constrained job-shop scheduling. International Journal of Simulation Modelling, 17(1), 147-158.