SINGLE MACHINE SCHEDULING WITH BATCH DELIVERY TO MULTIPLE CUSTOMERS IN A STAR-SHAPED NETWORK

In this paper, we consider the scheduling problem in which the jobs are first processed on a single machine and then delivered in batches by a single vehicle with limited capacity to the respective customers located at the vertices of a star-shaped network. The goal is to minimize the makespan. We present a 3/2-approximation algorithm for the identical job size case and a 2-approximation algorithm for the non-identical job sizes case.

MoreLess

Year of publication:	2013
Authors:	WANG, LEIYANG ; LIU, ZHAOHUI
Published in:	Asia-Pacific Journal of Operational Research (APJOR). - World Scientific Publishing Co. Pte. Ltd., ISSN 1793-7019. - Vol. 30.2013, 01, p. 1250048-1
Publisher:	World Scientific Publishing Co. Pte. Ltd.
Subject:	Scheduling \| batch delivery \| star-shaped network \| approximation algorithm

More details

Extent:	application/pdf text/html
Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://ebvufind01.dmz1.zbw.eu/10010882947