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

被引：3
|
作者：
Wang, Leiyang [1 ]
Liu, Zhaohui [1 ]
机构：
[1] E China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China
来源：
ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH | 2013年 / 30卷 / 01期
基金：
中国国家自然科学基金;
关键词：
Scheduling; batch delivery; star-shaped network; approximation algorithm; JOB; ALGORITHM;
D O I：
10.1142/S0217595912500480
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
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.
引用
收藏
页数：9
相关论文
共 50 条
  • [1] Single machine scheduling with job delivery to multiple customers
    Dong, Jianming
    Wang, Xueshi
    Hu, Jueliang
    Lin, Guohui
    JOURNAL OF SCHEDULING, 2018, 21 (03) : 337 - 348
  • [2] Single machine scheduling with job delivery to multiple customers
    Jianming Dong
    Xueshi Wang
    Jueliang Hu
    Guohui Lin
    Journal of Scheduling, 2018, 21 : 337 - 348
  • [3] Manufacture and Delivery Scheduling for Multiple Customers on a Single Machine with Availability Constraint
    Fan, Jing
    Proceedings of the 6th International Workshop of Advanced Manufacturing and Automation, 2016, 24 : 273 - 276
  • [4] BATCH DELIVERY SCHEDULING ON A SINGLE-MACHINE
    CHENG, TCE
    GORDON, VS
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1994, 45 (10) : 1211 - 1215
  • [5] Single batch machine scheduling with deliveries
    Cheng, B. -Y.
    Leung, J. Y. -T.
    Li, K.
    Yang, S. -L.
    NAVAL RESEARCH LOGISTICS, 2015, 62 (06) : 470 - 482
  • [6] HEURISTICS FOR PARALLEL MACHINE SCHEDULING WITH BATCH DELIVERY CONSIDERATION
    Wang, Leiyang
    Liu, Zhaohui
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2014, 10 (01) : 259 - 273
  • [7] Permutation Flow Shop Scheduling With Batch Delivery to Multiple Customers in Supply Chains
    Wang, Kai
    Luo, Hao
    Liu, Feng
    Yue, Xiaohang
    IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS, 2018, 48 (10): : 1826 - 1837
  • [8] Single-machine batch delivery scheduling with an assignable common due window
    Yin, Yunqiang
    Cheng, T. C. E.
    Hsu, Chou-Jung
    Wu, Chin-Chia
    OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2013, 41 (02): : 216 - 225
  • [9] Single machine batch scheduling with release times and delivery costs
    Selvarajah, Esaignani
    Steiner, George
    Zhang, Rui
    JOURNAL OF SCHEDULING, 2013, 16 (01) : 69 - 79
  • [10] Single machine batch scheduling with release times and delivery costs
    Esaignani Selvarajah
    George Steiner
    Rui Zhang
    Journal of Scheduling, 2013, 16 : 69 - 79
12345