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

作     者：Wang, Leiyang Liu, Zhaohui 

作者机构：E China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China 

出 版 物：《ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH》 (亚太运筹学杂志)

年 卷 期：2013年第30卷第1期

页      面：1250048-1250048页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：National Natural Science Foundation of China Fundamental Research Funds for the Central Universities of China 

主　　题：Scheduling batch delivery star-shaped network approximation algorithm 

摘      要：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.