本文主要探討節省法為基礎之分支定界法以決定機器合適度區間之零工式批量排程問題。此論文將環境以三種相關的單位作探討，由單位小到大分別為Operation、Batch、Period。Operation為每個工件在指定機台的操作。將Operation依工件大小總和、工件族等特性依特定規則組合並同時送進機台加工稱為Batch。Period為機台此次添加物料至下一次添加物料的時間段，Period會根據物料消耗的多寡決定服務多少Batch。 我們提出一個分支定界演算法去尋找這個問題的佳解。將利用Proposition以job size及release time計算各種Operation組合的節省面積。每個節點都會計算input operation及output operation的節省面積後得到多個batch，並在input batches及output batches中各選出一個指派到加工順序中成為一個節點，將所有指派可能舉出後便完成分支。 本論文依照環境設計出分離圖，分離圖上的分離弧線會依照節點的排程狀況更動，當找到起源點至終節點的最長路徑可得此節點的lower bound。得到可行解之節點的最長路徑並同Upper bound比較，可得目前已知最佳解。 最後，我們驗證節省法對物料消耗及尋找批量組合有不錯的表現。並發現節省法可降低批量的列舉數，分離圖計算出最長路徑後也明顯的提高砍支的數目。因此證明此演算法可快速及有效地找到此環境中表現優異的可行解。 ;This thesis is mainly designed with a saving method-based branch-and-bound algorithm for machine eligibility period determination problem on job shop batch processing. We discuss the environment in terms of Operation, Batch and Period. Operation is the processing of each job on the designated machine. Combining Operations according to the characteristics of sum of job size, family, etc., combined with specific rules and processed by the machine at the same time is called Batch. Period is the time interval from when the machine starts adding materials to the next time when materials are added. The amount of materials consumed determines how many batches are served by one period. We propose a branch and bound algorithm to find an excellent solution. Proposition will be used to calculate the area savings of multiple operation combinations with job size and release time. Each node will calculate the saving area of input operations and output operations to get batch. Select one of the input batches and output batches and assign them to the processing sequence to become a node. After all possible assignments are listed, the branch is completed. This thesis designs a disjunctive graph according to the problem, and the disjunctive arc on the disjunctive graph will change according to the scheduling status of the node. The longest path from the start point to the end point can get the lower bound of this node. Comparing the longest path of the feasible solution with the upper bound, we can see that the final solution has been obtained. Finally, we verify that the saving method has a good performance on material consumption and finding batch combinations. It is found that the saving method can reduce the enumeration number of the batch. The longest path of the disjunctive graph also significantly increases the number of cut branches. Therefore, it is proved that this algorithm can quickly and effectively find feasible solutions with excellent performance in this environment.
