[en] We consider a robotic flowshop model in which a single robot is responsible for the transportation of parts between machines and the amount of time that a part spends on a machine must be comprised in some predefined interval. The objective is to find a feasible schedule with minimal cycle time. Many researchers have proposed nonpolynomial solution methods for a variety of closely related robotic flowshop scheduling problems. This paper provides a proof that a basic version of this problem is strongly NP-Complete.
Disciplines :
Production, distribution & supply chain management Quantitative methods in economics & management
Author, co-author :
Crama, Yves ; Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Van de Klundert, Joris
Language :
English
Title :
Robotic flowshop scheduling is strongly NP-complete
