本研究探討具批量流(lot streaming)與等候時間限制(limited waiting time)特性的雙機流程型生產（two-machine flow shop）排程問題，以極小化完成時間為目標。批量流將工作分割成數個子批量（sublot）或轉運批（transfer batch），以便一製程完成後，可立刻送至下一製程，繼續處理加工，而不需等到整個工作完成後再移送至下一個製程。由於同一工作能在不同的製程上同時處理，可達到作業重疊(operation overlap)，縮短工作的完成時間。本研究討論子批量為連續型態(continuous-sized sublots)的批量流問題。存在於任二個製程間的等候時間窗口為一相依時間，等候時間限制前一製程完成後，在窗口時間的上限內必須進行下一製程。 本研究沿襲相關文獻使用的二步驟方式，求解多產品排程問題。首先針對單一產品問題提出一線性規劃模式(linear programming model)，並延伸幾何級數型態解(geometric form solution)至具等候時間限制的環境，求得最佳的子批量分割與最小完成時間。爾後再將單一產品問題求得的子批量引用到多產品問題中，提出一為枝界法(branch-and-bound algorithm)的啟發式演算法，求得一多產品加工順序與最小完成時間。 本研究針對提出的枝界法進行下列的實驗和資料分析，驗證演算法的正確性和效率。透過以下二個特例：不具批量流特性的問題(Yang and Chern, 1995)，和等候時間上限無限大的問題(Vickson, 1995)，證實枝界法的正確性。一般狀況下的實驗結果顯示，運用枝界法求得的解非常近似最佳解，且大部分為最佳解；經由枝界法求解過程中產生的節點數顯著比窮舉少非常多，當等候時間的上限增加時，產生的節點數會隨之減少，求解的速度會隨之增加。 This study treats the optimal lot streaming problem to minimize the makespan for multiple products in a two-machine flow shop with limited waiting time constraint. Lot streaming is the process of creating sublots (or transfer batches) to move the completed portion of a production sublot to downstream machines so that operations can be overlapped. Limited waiting time constraint means that for each product the waiting between two machines cannot be greater than a given upper bound. This problem is studied allowing continuous-sized sublots. We use two steps to solve lot streaming and scheduling of multiple products problem. First, a linear programming model and the optimal geometric form solution are proposed to find the optimal lot streams to minimize makespan for each product. Then, we develop a heuristic which is a branch-and-bound algorithm for the multiple products problem to find a sequence of products to minimize makespan under the assumptions that the optimal set of sublot sizes is given from each single product problem. Properties of machine dominance and revised Johnson’s rule are derived and implemented in the proposed algorithm for eliminating nodes efficiently in the branching tree. The following computational analyses are conducted for model validation and algorithm performance. (1) Validate the branch-and-bound algorithm by examples of two special cases: the problems with infinite waiting time constraint (Vickson, 1995) as well as the problem without lot streaming (Yang and Chern, 1995), namely, the whole product is a single lot. The same optimal solution can be found by the proposed algorithm. (2) Computation experiences indicate that this heuristic can deliver close-to-optimal solutions for this problem and find the optimal solutions for most of tests. The number of averaged generated nodes by the proposed algorithm is seen to be extremely small compared with the number of total enumerative nodes in branching tree. When the upper bound of waiting time is increased, the number of averaged generated nodes is decreased and the optimal solution is found fast.
