An efficient bicriteria algorithm for stable robotic flow shop scheduling

Ada Che, Vladimir Kats, Eugene Levner

科研成果: 期刊稿件文章同行评审

34 引用 (Scopus)

摘要

We consider a flow shop for processing single type of parts serviced by a single robot. The robot transportation times are allowed to have small perturbations. We treat the robotic flow shop scheduling problem considering stability of its schedule where the robot route is fixed and the processing durations of parts are to be specified from given intervals. The stability radius of a schedule is defined as the largest quantity of variations in the transportation times within which the schedule can still be executed as expected. We consider the bicriteria optimization problem which consists of minimizing the cycle time and maximizing the stability radius. The objective is to handle the two criteria simultaneously, that is, to find their Pareto front. We propose a new strongly polynomial algorithm for finding the minimum cycle times for all possible values of stability radius with time complexity of O(m4), where m is the number of processing machines in the flow shop. This implies that we can find the entire Pareto front of the problem in O(m4) time.

源语言英语
页(从-至)964-971
页数8
期刊European Journal of Operational Research
260
3
DOI
出版状态已出版 - 1 8月 2017

指纹

探究 'An efficient bicriteria algorithm for stable robotic flow shop scheduling' 的科研主题。它们共同构成独一无二的指纹。

引用此