A Survey of Algorithms for Single and Multi-Objective Unrelated Parallel-Machine Deterministic Scheduling Problems

單目標與多目標凖則之平行機台確定性排程問題求解方法研究

Michele Pfund ； John W. Fowler ； Jatinder N. D. Gupta

《工業工程學刊》 21卷3期 (2004/05) Pp. 230-241

https://doi.org/10.29977/JCIIE.200405.0003

摘要

本研究整理傳統解決不相關平行機台排程問題的相關文獻，匯整關於總作業時間跨距、總加權完成時間、最大的延誤時間、總延誤時間、總提早完成時間、延誤時間，以及多標準結果量測指標的演算法，但回顧現有演算法中往往受限於確定性問題，以及不考慮整備時間、優序問題與問題之相關附帶條件。經本研究可知，即使對於傳統的問題，已針對總作業時間跨距最小化進行廣泛的研究，但其中關於作業特性，如：寬裕時間、連續相關整備時間和優序問題仍然存在相當的研究空間，而對於不相關平行機台排程問題的求解，包括延誤工作數、延誤工作數加權值、總延誤時間和總加權延誤時間的最小化的研究卻有著相當的限制。

關鍵字

排程 ； 平行機台 ； 多目標排程

並列摘要

This paper surveys the literature related to solving traditional unrelated parallel-machine scheduling problems. It compiles algorithms for the makespan, total weighted sum of completion times, maximum tardiness, total tardiness, total earliness and tardiness, and multiple criteria performance measures. The review of the existing algorithms is restricted to the deterministic problems without setups, preemptions, or side conditions on the problem. Even for such traditional problems, this survey reveals that while makespan minimization has been fairly widely studied, problems that include processing characteristics such as release times, sequence dependent setups, and preemptions remain largely unstudied. Research in solving unrelated parallel-machine scheduling problems involving the minimization of the number of tardy jobs, weighted number of tardy jobs, total tardiness, and total weighted tardiness is quite limited.

並列關鍵字

scheduling ； parallel machines ； multi-objective scheduling

參考文獻

Aarts, E.,P. J. Van Laarhoven(1985).Statistical cooling: A general approach to combinatorial optimization.Philips Journal of Research.40,193-226.

Adamopoulos, G.,C. Pappis(1998).Scheduling under a common due date on parallel unrelated machines.European Journal of Operational Research.105,494-501.

Afrati, F.,E. Bampis, C. Kenyon,I. Milis(2000).APTAS for the average weighted completion time problem on unrelated machines.Journal of Scheduling.3,323-332.

Armacost, R.,A. Salem(1999).IERC Conference Proceedings.

Azizoglu, M.,O. Kirca(1999).Scheduling jobs on unrelated parallel-machines to minimize regular total cost functions.IIE Transactions.31,153-159.