本研究主旨為探討一平行機台排程問題，其作業具迴流特性，且迴流時間需滿足最大與最小時間延滯之限制;其機台具可用時間與合適度限制，目標為使總完工時間最小化。每個作業可重複於同一機台加工多次，但兩次重複加工之間隔時間受到時間延滯(Time Lags)的限制。每個機台只有某些時間區段可以被安排處理工作，每個工作也只能被安排在某些特定的機器上。 我們設置虛擬工作取代各機台不可被使用的時間，並將問題分成兩個階段： (1)提出一個分枝界限演算法搜尋可行的作業與機台指派組合，利用機台合適度限制進行分枝，發展定界法則提昇演算效率，並將指派結果以分離圖(Disjunctive Graph)表示；(2)利用先前研究提出的分枝定界法(沈國基與廖祿文，2007)求解(1)所得結果之排程解，即分別求解m個單機台排程問題，並以最後完工的作業作為總完工時間。 實驗的分析顯示，在總作業數大於五且機器合適度比率為八十的情境下，定界法則可刪去百分之八十以上的節點，顯著地提昇演算法的效率。我們提出的演算法可用於求解10個作業與3台機器的排程問題，並可獲得最佳解。 In this paper we study the problem of scheduling recirculation jobs on identical parallel machines with eligibility and availability restrictions when minimizing the makespan. Namely, each job may visit a machine more than once and is only allowed to be processed on specific machines; each machine is not always available for processing. Besides, minimal and maximal time lag constraints on the starting time of each reentrant job are also considered. We develop two branch and bound algorithms to solve the scheduling problem optimally. One is to deal with the jobs allocation problem with machine eligibility, and the other is to schedule the sequence on each allocated machine with minimal and maximal time lags constraints. We introduce a dummy job to denote each machine unavailable interval, and propose the first branch and bound algorithm which uses the depth first strategy to allocate jobs. We transform the scheduling problem corresponding to each leaf node into m single machine problems, which can be represented by a disjunctive graph. Finally, we use the second branch and bound algorithm adopted from Sheen and Lao (2007) for obtaining the optimal solution for each single machine problem to find the maximum makespan. Computational analysis shows that the eliminating rules proposed is effective and can eliminate more than 80% node when the total operation number is larger than 5 with eighty percent in generating machine availability by the branch and bound algorithm. Our algorithm can get the optimal solution for the problem with up to 10 operations and 3 machines.
