Online production planning to maximize the number of on-time orders
| Autor: | Nicholas G. Hall, Marc E. Posner, Chris N. Potts |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
021103 operations research Competitive analysis Computer science 0211 other engineering and technologies General Decision Sciences 02 engineering and technology Management Science and Operations Research Upper and lower bounds Set (abstract data type) Production planning Complete information Theory of computation Online algorithm |
| Popis: | We consider a production planning problem with two planning periods. Detailed planning occurs in the first period, when complete information is known about a set of orders that are initially available. An additional set of orders becomes available at the start of the second planning period. The objective is to maximize the number of on-time orders. We derive an upper bound on the competitive ratio of any deterministic online algorithm, relative to the performance of an algorithm with perfect information about the second set of orders. This ratio depends on the relative lengths of the two planning periods. We also describe an efficient algorithm that delivers a solution which asymptotically achieves this upper bound ratio as the number of jobs becomes large. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|