差異化生產流程之批次排程

Abstract

本篇論文探討一個三機台兩階段之差異化流線型機台組之生產模型，其包含一台主要機台與兩台專用機台。所有工作都包含二項作業，工作的第一項作業在第一階段的處理當中皆共享同一主要機台，而在第二階段當中，工作的第二項作業即由該工作所屬之專用機台處理之。在第一台機台上，所有的批次處理前皆需要一個固定的準備時間。本篇論文考慮二種批次處理的形式，分別為可相容的與不可相容的批次處理。在某些情況中，我們假設二種類型工作的執行順序已經給定且不可更動。探討之目標函數是要最小化最大完工時間。針對兩類批次形式，我們分別提出動態規劃演算法求取最佳解。另外，我們也利用此兩個演算法求取未給定執行順序之原始問題最佳解之下界值。

This thesis considers a three-machine two-stage differentiation flowshop to minimize the makespan. The flowshop comprises a common machine on stage-one and two independent dedicated machines on stage-two. All jobs consist of two operations, the first one is performed on the stage-one machine and the second is performed on the stage-two machine. All jobs share, and compete for, the common stage-one machine. A constant setup time is required whenever a batch is formed on the stage-one critical machine. Two different modes of batch composition, compatible and incompatible, are investigated. We also assume that the sequences of two types of jobs are fixed. The objective function to minimize is the makespan, or the maximum completion time. We proposed two polynomial-time dynamic programming algorithms for optimally solving the problems with compatible batching and incompatible batching, respectively. We then deploy the dynamic programming algorithms for computing lower bounds of the original problem without the assumption of given job sequences.