Approximation algorithms for two-machine open shop scheduling with batch and delivery coordination

We consider a scheduling problem with batch and delivery coordination. There are n jobs to be firstly processed by a two-machine open shop at a manufacturing facility, then be delivered to a common customer area by only one vehicle, which is initially located at the facility and has a capacity of c. The objective is to minimize the time when all jobs are completed and delivered to the customer area and the vehicle returns to the facility. For general c, we present a polynomial time approximation algorithm with a worst case ratio of 2. For the case when the vehicle can take only one job in each shipment, we show that there exists a 3/2-approximation algorithm. Crown Copyright (C) 2013 Published by Elsevier B.V. All rights reserved.