本研究主旨在探討單一批次加工機台在工件具時間窗口限制下極小化完工時間之排程問題。此單一機台具有固定的批次容量上限，每個工件具有一定的釋放時間和工件大小。在工件被釋放後必須在特定時間內開始加工；此特性稱為時間窗口。 我們建立一多層分離圖來表示此排程問題。在多層分離圖中，上層的批次節點之間已事先給定了表示加工順序的連結弧線；下層的每個工件節點和上層所有批次節點間皆有往來的虛擬弧線以此表示待定的指派關係。我們提出一個分支定界演算法去選定層間不同的虛擬弧線成為連結弧線來尋找這個問題的一個最佳解。 ;We study a scheduling problem on the single batch processing machine to minimize the makespan. The single batch processing machine has a stable batch capacity indicating the total size of any formed batch cannot exceed the capacity. Each job has a time window to indicate the maximum waiting time of the job. We establish a multiple-layer disjunctive graph to represent this scheduling problem. In a multiple-layer disjunctive graph, the conjunctive arcs in the upper-layer have been given to represent the processing sequence of batch nodes. The disjunctive arcs in the inter-layer represent the problem of the assignment of jobs to the batches. We purpose a branch and bound algorithm to solve the problem.
