Fast Algorithms for Basic Supply Chain Scheduling Problems
| Autor: | Badri Mamporia, Nodari Vakhania |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
time complexity
Computer science General Mathematics 0211 other engineering and technologies Scheduling (production processes) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Release time batch Computer Science (miscellaneous) supply chain scheduling Fixed cost Engineering (miscellaneous) Time complexity 021103 operations research algorithm Unit of time lcsh:Mathematics Supply chain scheduling lcsh:QA1-939 Delivery cost 010201 computation theory & mathematics Order (business) release time delivery Algorithm |
| Zdroj: | Mathematics, Vol 8, Iss 1919, p 1919 (2020) Mathematics Volume 8 Issue 11 |
| ISSN: | 2227-7390 |
| Popis: | 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&ge D. For the case 0< 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|