Abstract
傳統的雙機流水型排程問題由於基本的假設太過於簡化，以至於無法完全成功地應用在賓務上。所以，本文將探討幾個更一般化之雙機流水型排程問題：工作需要回復再處理之排程問題、工作在機器間的等待時間具有上限之排程問題、工作在機器間需要運送時間或是工作的處理時間與其等待時間具有相關性之排程問題。這些經過推廣後之雙機流水型排程模式可應用於橋樑建設、半導體、鋼鐵、食品與化學工業的作業排程上。所以，在本文中我們將探討上述之排程問題，證明NP-hardness及相關之理論性質，並設計解決。Since Johnson, in his pioneering work, proposed a polynominaltime algorithm for the two-machine flowshop scheduling problem.The flowshop scheduling problems have been studied extensively.However, due to the simplicity of the convertional models, theycan not be successfully implemented in some practicalscheduling problem with reprocessing operations, the schedulingproblem with limited waiting time constraints, the schedulingproblem with processing time linearly dependent on job waitting-time. These extensions have some practical applications inbridge construction, semiconductor manufacturing,metallurgical process, food production and chemical industry.We show that these problems are Np-hard. We also derive sometheoretical results and propose some efficient algorithms forsolving them.