Optimal scheduling of a single-supplier single-manufacturer supply chain with common due windows
Journal
IEEE Transactions on Automatic Control
Journal Volume
55
Journal Issue
12
Pages
2767-2777
Date Issued
2010
Author(s)
Abstract
We study a supply chain scheduling control problem involving a single supplier, a single manufacturer and multiple retailers, where the manufacturer with limited production capacity can only take some of the orders of the retailers. The manufacturer aims to maximize its profit, which is a function of the storage time, storage quantity, order sequence dependent weighted storage costs, and idle time of the orders to be accepted. We formulate the problem as a two-machine common due windows proportionate flow shop scheduling problem. We show that the problem is NP-hard. We provide the first pseudo-polynomial algorithm to optimally solve the problem. We show that for an accepted set of orders the shortest processing time earliest permutation schedule yields an optimal schedule. We prove that we can reduce the latest due dates of the due windows, which are given parameters, for minimizing the computational effort. We establish a tight upper bound on the enumeration process to manage the order idle time. We eliminate the need for generating all the optimal partial schedules to obtain an optimal solution, thus reducing the running time of our algorithm for solving the problem. We computationally tested the algorithm and the results show that the algorithm can solve large-sized problems very efficiently. ? 2006 IEEE.
Subjects
NP-hardness; operations research; optimal control; scheduling
Other Subjects
Common due-window; Computational effort; Due dates; Due-window; Idle time; NP-hard; NP-hardness; Optimal controls; Optimal schedule; Optimal scheduling; Optimal solutions; Permutation schedules; Production capacity; Proportionate flow shop; Pseudopolynomial algorithms; Running time; Sequence-dependent; Shortest Processing Time; Storage costs; Storage time; Supply chain scheduling; Upper Bound; Algorithms; Control; Hardness; Manufacture; Operations research; Optimization; Profitability; Supply chain management; Supply chains; Problem solving
Type
journal article