 A combined robot selection and scheduling problem for flow-shops with no-wait restrictionsDvir Shabtay, Kfir Arviv, Helman Stern and Yael Edan Omega, 2014, vol. 43, issue C, 96-107 Abstract: This paper addresses a bicriteria no-wait flow-shop scheduling problem with multiple robots transferring jobs between pairs of consecutive machines. The robots share an identical track positioned alongside the machine transfer line. Each robot is assigned to a portion of the tract from which it performs job transfers between all reachable machines. We assume that job processing times are both machine and job independent, that jobs are not allowed to wait between two consecutive machines and that machine idle times are not allowed. We define a combined robot selection and scheduling problem (RSSP) for a set of Q non-identical robots characterized by different costs and job transfer and empty movement times. A solution to the RSSP problem is defined by (i) selecting a set of robots, (ii) assigning each robot to a portion of the track, and (iii) scheduling the robot moves. We define a robot schedule as feasible if all the jobs satisfy the no-wait condition and there are no machine idle times. The quality of the solutions are measured by two criteria (performance measures): makespan and robot selection cost. We study four different variations of the RSSP,one which is shown to be solvable in polynomial time while the other three turn out to be NP-hard. For the NP-hard, we show that a pseudo-polynomial time algorithm and a fully polynomial approximation scheme exists, and derive three important special cases which are solvable in polynomial time. The RSSP has aspects of robot selection, machine-robot assignment and robot movement scheduling. We believe this is the first time that this type of problem has been treated in the literature, and addresses a very important problem in multiple robotic systems operation. Our contribution lies in the formulation, methodology, algorithms for solution and complexity results which jointly treats all aspects of the problem simultaneously without the need to defer to heuristic decomposition methods. Keywords: Scheduling; Flow-shop; No-wait restriction; Robotic flow-shop; Makespan; Bicriteria shortest path problem (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:43:y:2014:i:c:p:96-107 Ordering information: This journal article can be ordered from DOI: 10.1016/j.omega.2013.07.001 Access Statistics for this article Omega is currently edited by B. Lev More articles in Omega from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.