Semi-online two-level supply chain scheduling problems

Igor Averbakh*, Mehmet Baysan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


We consider two-level supply chain scheduling problems where customers release jobs to a manufacturer that has to process the jobs and deliver them to the customers. Processed jobs are grouped into batches, which are delivered to the customers as single shipments. The objective is to minimize the total cost which is the sum of the total flow time and the total delivery cost. Such problems have been considered in the off-line environment where future jobs are known, and in the online environment where at any time there is no information about future jobs. It is known that the best possible competitive ratio for an online algorithm is 2. We consider the problem in the semi-online environment, assuming that a lower bound P for all processing times is available a priori, and present a semi-online algorithm with competitive ratio 2D/D+p where D is the cost of a delivery. Also, for the special case where all processing times are equal, we prove that the algorithm is 1.045,√2-u/u competitive, where u is the density of the instance.

Original languageEnglish
Pages (from-to)381-390
Number of pages10
JournalJournal of Scheduling
Issue number3
Publication statusPublished - Jun 2012
Externally publishedYes


Acknowledgements This work was supported by a grant from the Natural Sciences and Engineering Research Council of Canada (NSERC) to Igor Averbakh.

FundersFunder number
Natural Sciences and Engineering Research Council of Canada


    • Competitive analysis
    • Semi-online algorithm
    • Supply chain scheduling


    Dive into the research topics of 'Semi-online two-level supply chain scheduling problems'. Together they form a unique fingerprint.

    Cite this