کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
474799 699141 2009 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Minimizing the bicriteria of makespan and maximum tardiness with an upper bound on maximum tardiness
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Minimizing the bicriteria of makespan and maximum tardiness with an upper bound on maximum tardiness
چکیده انگلیسی

This paper studies the flowshop scheduling problem with a complex bicriteria objective function. A weighted sum of makespan and maximum tardiness subject to a maximum tardiness threshold value is to be optimized. This problem, with interesting potential applications in practice, has been sparsely studied in the literature. We propose global and local dominance relationships for the three-machine problem and a fast and effective genetic algorithm (GA) for the more general mm-machine case. The proposed GA incorporates a novel three-phase fitness assignment mechanism specially targeted at dealing with populations in which both feasible as well as infeasible solutions might coexist. Comprehensive computational and statistical experiments show that the proposed GA outperforms the two most effective existing heuristics by a considerable margin in all scenarios. Furthermore, the proposed GA is also faster and able to find more feasible solutions. It should be noted that when the weight assigned to maximum tardiness is zero, then the problem is reduced to minimizing makespan subject to a maximum tardiness threshold value. Heuristics for both problems have been provided in the literature recently but they have not been compared. Another contribution of this paper is to compare these recent heuristics with each other.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 36, Issue 4, April 2009, Pages 1268–1283
نویسندگان
, ,