數位商品的生產排程模式

Abstract

本研究對於多媒體商品提出一個新的生產排程模式。一個多媒體商品是由數個多媒體原件所組成，包含文字、聲音以及影像。與一般製造產品所需的部件或零件不同的地方在於，多媒體的商品具備共享以及重複利用的特性。我們將多媒體的原件以及最終商品分別視為傳統排程模式中的輔助性作業以及最終的產品。而我們同時定義當所有的輔助性作業都完工以後，最終產品才完工。因此，在我們的模型中，目標函數只考慮最終工作的完工時間，輔助性作業的完工時間不被納入目標式裡面。由於最終工作的生產排程仍然會被其輔助性作業的生產排程影響，我們所提出的生產模式可被視為一種給定順序限制下的生產排程問題。 本篇論文包含三個部分。第一部份主要探討單一機台環境下的生產模式，所有的輔助性作業以及最終工作都在此單一機台上執行。我們探討兩個目標函數，分別是最小化加權最終工作的完工時間以及最小化延遲工作的數量。對於最小化加權最終工作的完工時間之目標函數，既使我們給定所有的輔助性作業的處理時間、所有最終工作的處理時間以及所有最終工作的權重都為一單位，此問題仍然是NP-hard。如果給定所有的輔助性作業一個執行順序，則我們提出一個在多項式時間內可求得最佳解的演算法。對於最小化延遲工作的數量之目標函數，我們證明：給定所有的輔助性作業以及最終工作的處理時間都為一單位，而且每一個輔助性作業都剛好支援三個最終工作、每一個最終工作都只被一個輔助性作業的條件下，此問題仍然為strongly NP-hard。若我們定所有的輔助性作業以及最終工作的處理時間都為一單位，而且每一個輔助性作業都剛好支援兩個最終工作、每一個最終工作都只被一個輔助性作業的條件下，此問題則為NP-hard。 本篇論文的第二部份則把單一機台環境的生產模型推廣到平行專用機台的環境。同樣的，我們定義最終工作的完工時間為各平行專用機台上其所需的輔助性工作的完工時間的最大值。我們在平行專用機台環境下的生產模型只探討目標函數為最小化最終工作的加總完工時間。我們對於這個問題提出四種不同的整數規劃模型配合四種不同的決策變數。Model SV利用順序性的決策變數來描述各平行專用機台上的輔助性作業之間的相對執行順序。Model PV利用位置類型的決策變數來指定各個輔助性作業在某一個平行專用機台上是在第幾個位置被執行。Model TV利用時間索引類型的決策變數來指出某個輔助性作業是否在某個特定的時間點已經完工。Model ETV是根據Model TV，同時引入另一個時間類型的決策變數，該決策變數用來指出最終工作是否在某依特定的時間點已經完工，同時給予我們額外的資訊去設計其他限制式。根據以上所提出的四種整數規劃模型，我們分別提出相對應的Lagrangian relaxations，用來求取最佳解的上限值與下限值。 本篇論文的最後一個部分考慮前面所提的四種不同的整數規劃模型，我們提出三種Lagrangian relaxations方法來求取近似解。第一種方法根據兩個heuristic所得到之原問題的上限值，來更新Lagrange multipliers。第二種方法將原問題拆解成兩個多項式時間內可求解的子問題。第一個子問題可以不使用Lagrangian relaxations，利用前置處理得到原問題上下限值；第二個子問題可以利用多項式時間內的演算法求出最佳解。第三種方法將原問題拆解成m+1個子問題。 為了檢驗我們所提出的整數規劃模型與Lagrangian relaxations方法的效益與效率，我們設計一系列的實驗。測試資料是由多種參數所搭配組成。我們探討所需要花費的執行時間以及解的品質。經由這些實驗的結果，我們發現各種整數規劃模型以及Lagrangian relaxations方法的優缺點。

This study proposes a novel scheduling model based on the production of media objects. A media product comprises various types of components or objects, including text, audio, and video clips. Unlike components or parts in the manufacturing of substantial products, media objects can be shared and reused by several media products. This type of production necessitates to a scheduling model consisting of supporting operations and regular jobs that respectively correspond to media objects and media products. Because a regular job is complete when all of its supporting operations are finished, the objective functions account for only the completion times of regular jobs. The completion times of supporting operations are not considered in the calculation of objective values. Because the completion of a job must follow the completion of all its supporting operations, this scheduling model can be regarded as scheduling under a particular type of precedence constraints. This thesis consists of three parts. The rest part is focused on the manufacturing setting in which a single machine is available, and all of the supporting operations and regular jobs are processed on this machine. We examined two objective functions, i.e. the total weighted job completion time and the number of late jobs. To minimize the total weighted job completion time, the problem remains strongly NP-hard even if the processing times of all operations and all jobs are one and all job weights are one. For operations in which the processing sequence is given and fixed, we propose a polynomial time algorithm to determine an optimal schedule. In considering the objective function of the number of late jobs, we provide a strong NP-hardness proof for the special case in which the processing times of all operations and all jobs are one, and each operation supports at most three jobs and each job is supported by at most one operation. Another case, in which each operation supports at most two jobs and each job is supported by at most one operation, is proven to be ordinary NP-hard. The second part of this thesis addresses a generalized model involving parallel dedicated machines. A job is complete when all of its operations on each dedicated machines are complete. The objective function considered is the total job completion time. Four integer programming models equipped with different types of decision variables are proposed to formulate this problem. Model SV uses sequential variables that describe the relative positions between each pair of operations on the machines. Model PV uses positional variables for assigning operations to positions on the machines. Model TV uses time-indexed variables that indicate if an operation is complete at a special time point. Model ETV introduces another set of time-indexed variables into Model TV to enhance the constraint speciation. Based on four proposed integer programs, we developed four corresponding Lagrangian relaxations for determining the lower and upper bounds on the optimal solution values. The final part concerns different features of four proposed integer programming models. We suggest three solution procedures in the Lagrangian relaxations. The first solution procedure is based on two heuristics to obtain the upper bounds of the original problem and update the Lagrange multipliers by using the obtained upper bounds. The second involves decomposing the model into two sub-problems. One of the two sub-problems can obtain the lower and upper bounds through a polynomial-time pre-processing procedure before invoking the Lagrangian relaxations. The other sub-problem can acquire optimal solutions by applying a polynomial time solvable algorithm. The last procedure reduces the relaxed problem into m+1 sub-problems that are relatively easy to address. To examine the effectiveness and efficiency of the proposed integer programming models and the Lagrangian relaxations, we designed a series of computational experiments. Test instances in this study were generated by applying various combinations of processing times and supporting relations. We investigated the elapsed execution times and solution quality of the proposed models and approaches. Analyzing the numerical results reveals the advantages and disadvantages of the integer programming models and the Lagrangian relaxations.