| 摘要: | 本研究探討一個具有多層級作業結構的零工式排程問題（Job shop scheduling problem），同時最小化最大完工時間（Makespan）與層級延遲完成次數（Total number of tardy stage-outs）。其中，tardy stage-outs 為管理層常用之階段性進度評估指標。為處理此一特性，本研究建構分離弧線圖（Disjunctive graph），表示多層級作業間的先後順序與機台資源使用關係，並在指定層級設置虛擬終點以判斷是否如期完成。本研究提出一套分支定界（Branch and Bound）方法以解決此雙目標問題。在分支策略中，演算法會計算所有可排程作業的最早完成時間，據此選定機台，並從中篩選具最早啟動潛力的作業進行分支。分支前，根據目標層（Interest layers）與共同到期日（Common due date）條件，預先排除可能影響目標層準時性的非關鍵作業，以降低延遲風險。在下界估算部分，makespan 下界參考單機排程問題理論，評估每台機台在不可搶佔條件下的最早完成潛力，取最大者為全域下界。tardy stage-outs 部分，針對管理層關注的目標層，預估其最早完工時間，若已超出指定期限，即視為必然延遲，納入遲交下界計算。為提升搜尋效率，本研究設計兩項剪枝條件。第一，於分支前排除非目標層的作業；第二，比較節點下界與目前 Pareto 前緣中的可行解，若其被支配則直接剪除。實驗結果顯示，在多數測試實例中，節點數可減少逾九成，顯著提升效能。綜上所述，本研究方法可應用於多層級製程環境中兼顧長短期目標的排程問題，提供對應的部分 Pareto 前緣解集合，協助決策者於雙目標間進行權衡排程。;This study investigates a job shop scheduling problem with a multi-layered operation structure, aiming to minimize both the makespan and the total number of tardy stage-outs. Among these, tardy stage-outs are used by managers as a key indicator of short-term progress performance. To address this, a disjunctive graph is constructed to model the precedence relationships and machine resource constraints among operations across layers. Sink nodes are added at the end of designated layers to evaluate their on-time completion status.
A branch and bound method is proposed to explore the solution space efficiently. During branching, the algorithm first identifies the schedulable operation with the earliest possible completion time, selects its corresponding machine, and filters operations on that machine with the potential to start earliest. Prior to branching, operations that may delay the completion of interest layers are removed, based on the due dates specified for those layers and the common due date constraint, thereby reducing the risk of short-term violations.
For lower bound estimation, the makespan bound refers to a classical single-machine scheduling formulation. The lower bound for each machine is calculated under non-preemptive conditions, and the global makespan lower bound is taken as the maximum of these values. For tardy stage-outs, the evaluation focuses on layers of managerial interest. If the earliest possible completion time already exceeds the due date, the layer is considered inevitably tardy and contributes to the lower bound calculation.
To improve search efficiency, two pruning rules are developed. First, operations not associated with interest layers are excluded during branching. Second, nodes whose lower bound vectors are dominated by current Pareto-optimal solutions are pruned. Experimental results show that these pruning strategies significantly reduce the number of nodes explored, with reductions exceeding 90% in some cases, thereby enhancing computational performance.
The proposed algorithm is suitable for scheduling problems involving both long-term and short-term objectives in multi-layered environments. It is especially applicable to semiconductor manufacturing settings that emphasize stage-based progress control. Under the constraint of a user-specified allowance for tardy layers, the algorithm provides partial Pareto front solutions to support trade-off scheduling decisions. |
