具機台合不兼容系列時間窗口限制與適度決定之平行批次處理問題;Scheduling Parallel Batch Processing Machines with Incompatible Families, Time Window Con-straints and Machine Eligibility Determination

NCUIR > School of Management at National Central University > Graduate Institute of Industrial Management > Electronic Thesis & Dissertation > Item 987654321/88090

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/88090

Title:	具機台合不兼容系列時間窗口限制與適度決定之平行批次處理問題;Scheduling Parallel Batch Processing Machines with Incompatible Families, Time Window Con-straints and Machine Eligibility Determination
Authors:	阮恆江英;Anh, Nguyen Hang Giang
Contributors:	工業管理研究所
Keywords:	平行批次處理;時間窗口限制;機台合適度決定;分解法;儲蓄法;遺傳算法;Parallel batch processing machines;Time window constraints;Machine eligibility determination;Decomposition approach;Savings method;Genetic algorithm
Date:	2022-05-10
Issue Date:	2022-07-13 17:57:51 (UTC+8)
Publisher:	國立中央大學
Abstract:	本研究考慮了一個並行批量處理機器的問題，以在任意批量、不兼容系列、開始時間窗口的約束和適度決定下達到最小化製造時間。本研究首先通過混合整數程序化模型來格式化問題，並且也提供了所研究問題的下界。但因爲研究問題為NP-Hard且因應實務上須能解決大的問題，本研究亦將發展了一種基於分解的啟發式算法和進化算法，以便在計算時間作為一個側重點時獲得大規模問題的近似最優解。二維節約函數被引入來量化時間和容量空間被浪費的值。對於遺傳算法，我們提出了用於編碼的二維矩陣和一維表示，以及適當的二維交叉和突變以產生後代。此外，此遺傳算法旨在改善基於已開發分解的啟發式算法的解決方案品質，該啟發式被用作已開發遺傳算法的初始解。計算實驗表明，所提出的啟發式算法對於小規模問題的執行表現良好，並且可以在合理的計算時間內有效地處理大規模問題。此外，計算結果還表明，本研究提出的啟發式算法在答案品質 (Solution quality) 方面優於文獻中現有的啟發式算法。;This study considers a parallel batch processing machines problem to minimize the makespan under constraints of arbitrary lot sizes, incompatible families, start time windows, and machine eligibility determination. We first formulate the problem by a mixed-integer programming model and a lower bound for the studied problem is also provided. Due to the NP-hardness of the problem, we then develop a decomposition-based heuristic and an evolutionary algorithm to obtain a near-optimal solution for large-scale problems when computational time is a concern. A two-dimensional saving function is introduced to quantify the value of time and capacity space wasted. For the genetic algorithm, we propose a two-dimensional matrix and one-dimensional representation for encoding, and appropriate two-dimensional crossovers as well as mutations to generate offspring. In addition, the genetic algorithm aims to improve the quality of the solution found by the developed decomposition-based heuristic which is used as an initial solution for the developed genetic algorithm. Computational experiments show that the proposed heuristic algorithms perform well for small-size problems and can deal with large-scale problems efficiently within a reasonable computational time. Moreover, computational results also indicate that our proposed heuristics outperform an existing heuristic from the literature in terms of solution quality.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	73	View/Open

社群 sharing

Loading...