Research Article

A PTAS for single-machine scheduling with release dates and job delivery to minimize makespan

¹ School of Mathematics and Statistics, Zhengzhou University, 450001 Zhengzhou, Henan, PR China
² College of Information and Management Science, Henan Agricultural University, 450003 Zhengzhou, Henan, PR China

^* Corresponding author: lulingfa@zzu.edu.cn

Received: 29 December 2016
Accepted: 28 October 2018

Abstract

We consider the single-machine scheduling problem with release dates and job delivery to minimize makespan. Preemption is not allowed in the processing of the jobs. All jobs are first processed on a single machine and then delivered by a capacitated vehicle to a single customer. The vehicle can deliver at most c ≥ 1 jobs in each shipment. The round-trip transportation time between the machine and customer is a constant T > 0. The problem was proved to be strongly NP-hard and a 3/2-approximation algorithm was presented in the literature. In this paper we provide a polynomial-time approximation scheme (PTAS) for the problem.