用最大後悔值最小化求解生產排程問題

本研究的問題是研究多台平行機器排程問題(Parallel Machines Scheduling Problem)的最大後悔值最小化，並使求出的解的後悔值為最小。在現實世界中，舉凡工作的優先權、工作的執行時間、機器的老舊程度、工人的技術和經驗等等，都會影響排程的情形。但這些資料(或是參數)很難預先得知其精確值。本研究針對此一困難，使用穩健最佳化的概念來解決現實生活中不確定性資料的問題。本研究在分析此排程問題之後，發現可以將最大後悔值最小化的多台平行機器排程問題轉型為P||ΣC的指派問題，因此本研究將利用穩健指派問題的定義及Kasperski 提出的混合整數規劃模型來求解。本研究希望能使排程問題的求解模式更貼近現實面，對於生產排程決策能有所助益。

關鍵字

穩健排程；穩健指派；後悔值；穩健多機排程； ILS

並列摘要

This paper deals with the Min-max Regret optimization for Production scheduling problem. We deal with the Robust Parallel Machines Scheduling Problem. The objective is to obtain robust job scheduling with minimum maximal regret. Several factors in the real-world affects the production schedule, like priority, processing time, machines condition, workers’ skill and experience etc. However, the exact values of these data can not be known precisely in advance. The goal of this thesis is to handle imprecise input data and minimize the maximal regret for scheduling with more than one processor. We found this problem can be transformed into the P||ΣC assignment problem. Therefore, we introduce the Mixed Integer Programming model for the robust assignment problem from Adam Kasperski. We wish that the result can help managers on production scheduling to make better decisions.

並列關鍵字

Robust scheduling Problem ； Robust Assignment Problem ； Regret ； RPMSP ； ILS

參考文獻

[54] 林宇璠，物流中心訂單排序問題之研究，碩士論文，國立台北科技大學工業工程與管理研究所，台北，2010。

[53] 邱鵬憲，最小化總絕對完工時間差異之穩健單機排程，碩士論文，國立台北科技大學工業工程與管理研究所，台北，2010。

[1] Adam Kasperski, “Minmax Regret Minimum Assignment”, Fuzziness and Soft Computing, 2008, Volume 228/2008, 113-120.

[2] Adam Kasperski, “Sequencing Problem with the Total Flow Time Criterion”, Fuzziness and Soft Computing, 2008, Volume 228/2008, 183-195, DOI: 10.1007/978-3-540-78484-5_15.

[3] A. Kasperski, P. Zielin'ski, “An approximation algorithm for interval data minmax regret combinatorial optimization problems”, Information Processing Letters Volume 97, Issue 5, 2006, pp. 177-180.

國際替代計量

用最大後悔值最小化求解生產排程問題

未授權

主題瀏覽