政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/10280

政大典藏 > College of Commerce > Department of Business Administation > Periodical Articles > Item 140.119/10280

Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/10280

Title:	Evaluating A Posteriori Solution Techniques for Bi-criteria Parallel Machine Scheduling Problems
Authors:	J. W. Fowler;Kim W. M.;W. M. Carlyle;E. Gel;洪叔民 Fowler, John W.;Kim, Bosun;Carlyle, W. Matthew;Gel, Esma Senturk;Horng, Shwu-Min
Keywords:	multiple criteria combinatorial optimization;comparison measures;parallel machine scheduling
Date:	2005-01
Issue Date:	2008-11-25 10:46:32 (UTC+8)
Abstract:	The quality of an approximate solution for combinatorial optimization problems with a single objective can be evaluated relatively easily. However, this becomes more difficult when there are multiple objectives. One potential approach to solving multiple criteria combinatorial optimization problems when at least one of the single objective problems is NP-complete, is to use an a posteriori method that approximates the efficient frontier. A common difficulty in this type of approach, however, is evaluating the quality of approximate solutions, since sets of multiple solutions should be evaluated and compared. This necessitates the use of a comparison measure that is robust and accurate. Furthermore, a robust measure plays an important role in metaheuristic optimization for “tuning” various parameters for evolutionary algorithms, simulated annealing, etc., which are frequently employed for multiple criteria combinatorial optimization problems. In this paper, the performance of a new measure, which we call Integrated Convex Preference (ICP) is compared to that of other measures appearing in the literature through numerical experiments—specifically, we use two a posteriori solution techniques based on genetic algorithms for a bi-criteria parallel machine scheduling problem and evaluate their performance (in terms of solution quality) using different measures. Experimental results show that the ICP measure evaluates the solution quality of approximations robustly (i.e., similar to visual comparison results) while other alternative measures can misjudge the solution quality. We note that the ICP measure can be applied to other non-scheduling multiple objective combinatorial optimization problems, as well.
Relation:	Journal of Scheduling, 8(1), 75-96
Data Type:	article
DOI link:	http://dx.doi.org/10.1007/s10951-005-5316-4
DOI:	10.1007/s10951-005-5316-4
Appears in Collections:	[Department of Business Administation] Periodical Articles

Files in This Item:

File	Description	Size	Format
7596.pdf		389Kb	Adobe PDF2	998	View/Open

社群 sharing

Loading...