Transfer-robot task scheduling in flexible job shop
- PDF / 1,850,154 Bytes
- 11 Pages / 595.276 x 790.866 pts Page_size
- 34 Downloads / 186 Views
Transfer‑robot task scheduling in flexible job shop Andy Ham1 Received: 17 August 2019 / Accepted: 13 January 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper studies a simultaneous scheduling of production and material transfer in a flexible job shop environment. The simultaneous scheduling approach has been recently adopted by a robotic mobile fulfillment system, wherein transbots pick up jobs and deliver to pick-stations for processing, which requires a simultaneous scheduling of jobs, transbots, and stations. Two different constraint programming formulations are proposed for the first time for a flexible job shop scheduling problem with transbots, significantly outperforming all other benchmark approaches in the literature and proving optimality of the well-known benchmark instances. Keywords Robot task scheduling · Flexible job shop · Simultaneous scheduling · Constraint programming
Introduction A Robotic Mobile Fulfillment System (RMFS) is an automated, parts-to-picker storage system where robots bring pods with products to pick-stations. It is especially suited for e-commerce distribution centers with large assortments of small products and with strong demand fluctuations (Lamballais et al. 2017). However, installing an RMFS typically requires a multi-million dollar investment, most of which is spent on the robots that carry the pods (see Fig. 1). Amazon (2014), Alibaba (2017), and Berkshire Grey (2019) have employed mobile robots to deliver pods from staging areas to pick-station as pictured on Fig. 1a–c. Similarly, Ocado (2018) utilizes transbots to grab a crate, pull it up into their interior, and deliver to pick-station as pictured on Fig. 1d. One of the urgent needs in an RMFS is to efficiently operate the transfer-robots (transbot hereafter) to fetch pods and bring them to one of pick-stations. The transbots task schedule must be integrated with pick-stations and other resources such as induction-stations and discharging-stations. These two decisions (transbot-scheduling and station-scheduling) are interrelated and must be synchronized. The simultaneous scheduling of transbots and stations has been well studied in a job shop environment. The classic job shop scheduling * Andy Ham [email protected] 1
problem (JSP) schedules a set of jobs on a set of stations with the objective to minimize a maximum completion time over all jobs (CMAX), subjected to the constraint that each job has an ordered set of operations, each of which must be processed on a predefined station. In this new integrated approach, transbots perform a delivery task between two operations. However, a flexible job shop scheduling with transbot (FJSP+transbots) has rarely been studied. In particular, the subsequent station ID of each job, upon completing an operation, is known a priori in a JSP problem, which makes the transbot-scheduling relatively simple. However, a specific station ID is not predetermined in an flexible job shop scheduling problem (FJSP) since a job is processed on
Data Loading...
