固定工作順序條件下之排程問題

Abstract

在生產排程問題中，工作或訂單順序代表其在機器上之處理先後順序，而排程則是明確排定每一工作或訂單在各台機器上之開始與完工時間。對某些排程問題而言，工作順序的給定並不直接等同排程結果。在這類型的問題中，除了排序之外，尚有諸如批量、交織穿插、延後執行等決策問題需要考量。這類型的排程問題即使固定其工作順序仍值得探究。在給定工作順序後，這類型的排程問題可稱之為固定工作順序條件排程問題。本論文針對三個固定工作順序條件排程問題進行研究。

本論文首先探究之固定工作順序條件排程議題為兩階段組裝線流線型機組批量排程問題。此問題考量的組裝線流線型機組環境為：階段一配置 $m$ 台平行指定機器、階段二配置一台批量處理機器。給定 $n$ 筆工作或訂單順序，並考量總完工時間最小化的目標下，本研究提出一個 $O(mn+n^5)$ 時間複雜度之演算法。

第二個研究主題為兩階段差異化流線型機組排程問題。此問題考慮的差異化流線型機組環境為：階段一配置一台公用機器、階段二配置 $m$ 台平行指定機器。假設階段二的某平行指定機器 $M_l$ 擁有 $n_l$ 筆工作或訂單待處理。在分別給定 $m$ 台平行指定機器個別之工作或訂單順序，並考量總完工時間最小化的目標下，本研究提出一個 $O(m^2\prod_{l=1}^m n_l^{m+1})$ 時間複雜度之動態規劃演算法。

第三個研究議題為單機器雙子作業排程問題。此問題的工作或訂單皆為雙子作業，每個工作的兩個子作業間存在一個固定的延遲時間。本研究之目標為固定工作順序條件下最大完工時間最小化。關於此議題下的固定工作順序條件排程問題，其時間複雜度仍懸而未決，然本研究提出一個 $O(n^2)$ 時間複雜度演算法解決固定“子作業”順序條件排程問題。此外，三個多項式時間可解的特例狀況亦在本文中被提出探討。

In machine or shop scheduling, sequences of jobs or operations indicate the order of processing on machines while schedules explicitly specify the starting and completion times of activities on specific machines. For some problems, determining an optimal schedule from a given sequence may not be straightforward because another decision such as batching, interleaving, or idle time insertion is needed for optimality. In this study, three fixed-job-sequence problems are considered.

The first addressed problem is a two-stage assembly-type flowshop scheduling problem with batching considerations subject to a fixed job sequence. The assembly-type flowshop consists of $m$\ parallel dedicated machines at stage 1 and a batch machine at stage 2. The objective is to minimize the total completion time. A two-phase algorithm is developed to solve the studied problem in $O(mn+n^5)$\ time, where $n$\ is the number of jobs and $m$\ is the number of parallel dedicated machines arranged at stage 1.

In the second problem, total completion time minimization in a two-stage differentiation flowshop subject to fixed sequences of jobs per type is studied. The two-stage differentiation flowshop comprises a stage-1 common machine and $m$\ stage-2 parallel dedicated machines. The goal is to determine an optimal interleaved processing sequence of all jobs at stage 1. This study presents an $O(m^2\prod_{l=1}^m n_l^{m+1})$\ dynamic programming algorithm, where $n_l$\ is the number of type-$l$\ jobs. The running time is polynomial when $m$\ is constant.

In the third problem, the single-machine coupled-task scheduling, where the two tasks of each job are separated by an exact delay, is investigated. The aim is to schedule these coupled tasks to minimize the makespan subject to a given job sequence. Several intriguing properties of the studied problem are introduced. While the complexity status of the fixed-job-sequence problem remains open, an $O(n^2)$\ algorithm is proposed to construct a feasible schedule attaining the minimum makespan for a given permutation of $2n$\ tasks abiding by the fixed-job-sequence constraint. Three polynomially solvable cases and a complexity graph of the fixed-job-sequence problem are presented.