混合整數規劃求解平行機台下變動時窗工件之分割排程

The job-splitting scheduling of varying-time-window jobs on parallel machines by mixed integer programming

張文亭(Wen-Ting Chang)

指導教授 ： 洪一峯

國立清華大學/工學院/工業工程與工程管理學系/碩士(2013年)

摘要

本文的研究動機是來自於大量製造之接單式生產環境中所面對的生產計劃管理問題。在此生產環境下，決策者除了要能夠在收到詢問訂單時準確地衡量工廠是否有足夠的產能來滿足顧客的需求以及是否能準時在交期前完工。由於每張訂單都有其對應的生產時窗(為工件可開始加工時間與交期之間的時間區段)，因此決策者還要決定如何將已確認的訂單適當的分配到各平行機台上做加工使得所有手中的訂單都能如期交貨。本研究考慮了非等效平行機台的生產環境，並同時考慮不同工作換線時存在一段順序相依及機台相依的整備時間。為了使顧客訂單能在其生產時窗內完成，決策者通常必需將一個訂單分配到多個平行機台上同時加工。
本研究對兩個不同階層的生產計劃管理分別提出不同的求解方法。在訂單詢問與接收階段利用優先式最早交期之產能需求規劃法(preemptive earliest due date CRP approach)來判斷產能是否足夠應付需求，而在現場排程階段使用字典排序目標規劃法(lexicographic goal programming approach)來進行生產排程規劃。本論文的多目標規劃中考慮了兩個目標，首要目標是最小化總延遲時間，而次要目標為最小化總整備時間，因此本研究針對不同的目標分別建立兩個不同的混整數規劃函數。另外在現場排程階段，對於工作的分割性我們考量了兩個不同假設的模型:第一個模型是假設同一個機台上同一個工件最多只能分割成一個子工件，而第二個模型則假設同一個工件允許拆成多個子工件在同一機台上不同位置做加工。基於不同的假設環境，本研究用了兩個不同的建模技巧：模型一使用緊鄰變數(immediate-precedence variables)為主要決策變數，而模型二使用序列位置變數(sequence position variable)為主決策變數。
實驗結果顯示本研究提出的方法可以在有限的時間內找到有效率的排程。

關鍵字

生產規劃 ； 生產排程 ； 非等效平行機台 ； 順序相依整備時間 ； 機台相依整備時間 ； 工作可分割

並列摘要

This study is motivated by the production management problem found in many large-volume MTO systems. In such an environment, a decision maker has to evaluate the requested due dates if are capacity feasibility, and further, to determine how to distribute each confirmed order with arbitrary ready date and due date to parallel machines so that the demand quantity and the due date can be met. Sequence- and machine-dependent setup times in unrelated parallel machine systems are considered in this study. In order to finish promised orders on time, splitting the production items into parallel machines for simultaneous processing is necessary.
Two different approaches are proposed for the two hierarchical levels of production management – the preemptive earliest due date (PEDD) CRP approach in order entry level and the lexicographic goal programming approach in operational scheduling level. Two priority objectives are considered in the goal programming, the first priority is to minimize the total tardiness and the second priority is to minimize the total setup time. Therefore, two different mixed integer programming (MIP) formulations are proposed for the two priority objectives. Furthermore, two models with two different assumptions on job splitting are investigated in the operational scheduling level. Model 1 allows at most one setup for a job on a machine, while Model 2 allows multiple setups. Because of the assumption difference, the two models adopted two different modeling techniques of binary variables. The immediate-precedence variables modeling technique is used in Model 1; whereas, the sequence position variable modeling technique is used in Model 2.
The experimental result shows that the proposed approach can effectively and efficiently solves the problems.

並列關鍵字

production planning ； production scheduling ； unrelated parallel machine ； sequence-dependent setup time ； machine-dependent setup time ； job-splitting

參考文獻

Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C. and Sviridenko, M. (1999), “Approximation schemes for minimizing average weighted completion time with release dates”, 32-44.

Anagnostopoulos, G. C. (2002), “A Simulated Annealing Algorithm for the Unrelated Parallel Machine Scheduling Problem”, Automation Congress, 2002 Proceedings of the 5th Biannual World, 14, 115-120.

Arnaout, J-P, and Rabadi, G. (2008), “Rescheduling of Unrelated Parallel Machines under Machine Breakdowns”, International Journal of Applied Management Science, 1, 75-89.

Arnaout, J-P, Rabadi, G., and Musa, R. (2010), “A Two-Stage Ant Colony Optimization Algorithm to Minimize the Makespan on Unrelated Parallel Machines with Sequence-dependent Setup Times”, Journal of Intelligent Manufacturing, 21(6), 693-701.

Bank, J. and Werner, F. (2001), “Heuristic algorithms for unrelated parallel-machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties”, Mathematical and Computer Modeling, 33, 363-383.