Approximation algorithm for the on-line multi-customer two-level supply chain scheduling problem

被引：13
|
作者：
Averbakh, Igor [1 ]
Baysan, Mehmet [1 ]
机构：
[1] Univ Toronto Scarborough, Dept Management, Toronto, ON M1C 1A4, Canada
来源：
OPERATIONS RESEARCH LETTERS | 2013年 / 41卷 / 06期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Supply chain scheduling; On-line algorithm; Competitive analysis; Integrated production-distribution problems;
D O I：
10.1016/j.orl.2013.10.002
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
A manufacturer has to process jobs released on-line and deliver them to customers. Preemption is allowed. Jobs are grouped into batches for delivery. The sum of the total flow time and the total delivery cost is minimized. Deliveries to different customers cannot be combined. We present an on-line algorithm with the competitive ratio bounded by 3 + alpha, where alpha is the ratio of the largest processing time to the smallest processing time. (C) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码：710 / 714
页数：5
相关论文
共 20 条
  • [1] On-line Supply Chain Scheduling Problem with Capacity Limited Vehicles
    Han, B.
    Zhang, W. J.
    IFAC PAPERSONLINE, 2015, 48 (03): : 1539 - 1544
  • [2] Semi-online two-level supply chain scheduling problems
    Averbakh, Igor
    Baysan, Mehmet
    JOURNAL OF SCHEDULING, 2012, 15 (03) : 381 - 390
  • [3] Semi-online two-level supply chain scheduling problems
    Igor Averbakh
    Mehmet Baysan
    Journal of Scheduling, 2012, 15 : 381 - 390
  • [4] On-line supply chain scheduling problems with preemption
    Averbakh, Igor
    Xue, Zhihui
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 181 (01) : 500 - 504
  • [5] On-Line Job Shop Scheduling with Transfer Time in Supply Chain
    Chang, Gui-Juan
    2008 IEEE INTERNATIONAL CONFERENCE ON AUTOMATION AND LOGISTICS, VOLS 1-6, 2008, : 284 - 289
  • [6] On-line supply chain scheduling for single-machine and parallel-machine configurations with a single customer: Minimizing the makespan and delivery cost
    Han, Bin
    Zhang, Wenjun
    Lu, Xiwen
    Lin, Yingzi
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 244 (03) : 704 - 714
  • [7] An approximation algorithm for a supply-chain scheduling problem with an assignable common due window and holding time
    Zhang, Long
    Zhang, Yuzhong
    Bai, Qingguo
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (04) : 2167 - 2179
  • [8] An approximation algorithm for a supply-chain scheduling problem with an assignable common due window and holding time
    Long Zhang
    Yuzhong Zhang
    Qingguo Bai
    Journal of Combinatorial Optimization, 2022, 44 : 2167 - 2179
  • [9] Integrated Supply Chain Scheduling under Multi-Level Disruptions
    Sawik, T.
    IFAC PAPERSONLINE, 2015, 48 (03): : 1515 - 1520
  • [10] Application of an effective modified gravitational search algorithm for the coordinated scheduling problem in a two-stage supply chain
    Pei, Jun
    Liu, Xinbao
    Pardalos, Panos M.
    Fan, Wenjuan
    Yang, Shanlin
    Wang, Ling
    INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2014, 70 (1-4) : 335 - 348
12