Fast Algorithms for Basic Supply Chain Scheduling Problems

Nodari Vakhania and Badri Mamporia
Additional contact information
Nodari Vakhania: Department of Computer Sciences, Universidad Autónoma del Estado de Morelos, Cuernavaca 62209, Morelos, Mexico
Badri Mamporia: Muskhelishvili Institute of Computational Mathematics, Georgian Technical University, 0159 Tbilisi, Georgia

Mathematics, 2020, vol. 8, issue 11, 1-19

Abstract: A basic supply chain scheduling problem in which the orders released over time are to be delivered into the batches with unlimited capacity is considered. The delivery of each batch has a fixed cost D , whereas any order delivered after its release time yields an additional delay cost equal to the waiting time of that order in the system. The objective is to minimize the total delivery cost of the batches plus the total delay cost of the orders. A new algorithmic framework is proposed based on which fast algorithms for the solution of this problem are built. The framework can be extended to more general supply chain scheduling models and is based on a theoretical study of some useful properties of the offline version of the problem. An online scenario is considered as well, when at each assignment (order release) time the information on the next order released within the following T time units is known but no information on the orders that might be released after that time is known. For the online setting, it is shown that there is no benefit in waiting for more than D time units for incoming orders, i.e., potentially beneficial values for T are 0 < T < D , and three linear-time algorithms are proposed, which are optimal for both the offline and the online cases when T ≥ D . For the case 0 < T < D an important real-life scenario is studied. It addresses a typical situation when the same number of orders are released at each order release time and these times are evenly distributed within the scheduling horizon. An optimal algorithm which runs much faster than earlier known algorithms is proposed.

Keywords: supply chain scheduling; algorithm; batch; release time; delivery; time complexity (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/11/1919/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/11/1919/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:11:p:1919-:d:438690

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().