A new lower bound for flexible job shop scheduling problem with batching to minimize total tardiness and total number of tardy stage outs

NCU Institutional Repository > 管理學院 > 工業管理研究所 > 博碩士論文 > Item 987654321/97341

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: https://ir.lib.ncu.edu.tw/handle/987654321/97341

题名:	A new lower bound for flexible job shop scheduling problem with batching to minimize total tardiness and total number of tardy stage outs
作者:	吳啟昀;Wu, Chi-Yun
贡献者:	工業管理研究所
关键词:	彈性零工式排程問題;分離弧線圖;批次生產;Flexible job-shop;scheduling problem;conjunctive graph
日期:	2025-07-24
上传时间:	2025-10-17 11:09:41 (UTC+8)
出版者:	國立中央大學
摘要:	在半導體製程中，我們在彈性零工式排程問題(Flexible job shop scheduling problem)環境下，考慮的限制條件有批次處理(Batching)和順序相依整備時間 (Sequence-dependent setup time)，目標為最小化總延遲時間(Total tardiness)和 Total number of tardy stage-outs。這兩個目標的解可以通過分離圖(Conjunctive graph)來表示，其中每個工件(job)都具有多個層級(layer)，每個層級包含多個操作 (operation)，且總延遲階段數的目標會以圖層(layer)的方式呈現。為解決這一雙目標問題，本研究採用了NSGA-II演算法作為基於帕累托(Pareto-based)的方法來尋找最佳解。鄰域結構(Neighborhood structure)將被應用於突變運算子(Mutation operator)，並且包括兩種類型的移動(Move)，以及引入偏好值(preference value)來幫助我們的搜索過程。這些移動的可行性保證(Feasibility guarantees)將確保在移動後不會產生循環(Cycle)。此外，我們將提出針對兩個目標值新的下界(New Lower bounds)將確保在進行移動後不會增加目標值，並將利用新的下界和節省值(saving values)改善階層式移動分類(Hierarchy of moves)結果且應用於增強解的多樣性與效果。;In the semiconductor manufacturing process, we consider the Flexible Job Shop Scheduling Problem (FJSP) environment with two specific constraints: batch processing and sequence-dependent setup times. The objective is to minimize both the total tardiness and the total number of tardy stage-outs. Solutions for these two objectives can be represented using a conjunctive graph, where each job has multiple layers, each layer consists of multiple operations, and the objective of minimizing the number of tardy stage-outs is visualized through layered graph structures. To address this bi-objective optimization problem, we adopt the NSGA-II algorithm, a Pareto-based evolutionary approach for identifying optimal solutions. A neighborhood structure is applied within the mutation operator, incorporating two types of moves along with a preference value to guide the search process. The feasibility of these moves is guaranteed to prevent the creation of cycles in the graph. Moreover, we introduce new lower bounds for both objective functions to ensure that moves do not worsen the objective values after being applied. These new bounds, along with associated saving values, are used to improve the hierarchy of move classifications, thereby enhancing both solution diversity and solution quality.
显示于类别:	[工業管理研究所 ] 博碩士論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	20	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....