Abstract
We study the operations scheduling problem with delivery deadlines in a three-stage supply chain process consisting of (1) heterogeneous suppliers, (2) capacitated processing centres (PCs), and (3) a network of business customers. The suppliers make and ship semi-finished products to the PCs where products are finalized and packaged before they are shipped to customers. Each business customer has an order quantity to fulfil and a specified delivery date, and the customer network has a required service level so that if the total quantity delivered to the network falls below a given targeted fill rate, a non-linear penalty will apply. Since the PCs are capacitated and both shipping and production operations are non-instantaneous, not all the customer orders may be fulfilled on time. The optimization problem is therefore to select a subset of customers whose orders can be fulfilled on time and a subset of suppliers to ensure the supplies to minimize the total cost, which includes processing cost, shipping cost, cost of unfilled orders (if any), and a non-linear penalty if the target service level is not met. The general version of this problem is difficult because of its combinatorial nature. In this paper, we solve a special case of this problem when the number of PCs equals one, and develop a dynamic programming-based algorithm that identifies the optimal subset of customer orders to be fulfilled under each given utilization level of the PC capacity. We then construct a cost function of a recursive form, and prove that the resulting search algorithm always converges to the optimal solution within pseudo-polynomial time. Two numerical examples are presented to test the computational performance of the proposed algorithm.
Similar content being viewed by others
References
Ahuja RK, Magnanti TL and Orlin JB (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall: Upper Saddle River, NJ.
Alpan G, Ladier AL, Larbi R and Penz B (2011). Heuristic solutions for transshipment problems in a multiple door cross docking warehouse. Computers & Industrial Engineering 61 (2): 402–408.
Bard JF and Nananukul N (2009). The integrated production-inventory-distribution-routing problem. Journal of Scheduling 12 (3): 257–280.
Bertazzi L and Zappa O (2012). Integrating transportation and production: An international study case. Journal of the Operational Research Society 63 (7): 920–930.
Brotcorne L, Hanafi S and Mansi R (2009). A dynamic programming algorithm for the bi-level knapsack problem. Operations Research Letters 37 (3): 215–218.
Garey MR and Johnson DS (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company: New York.
Guinet A (2001). Multi-site planning: A transshipment problem. International Journal of Production Economics 74 (1–3): 21–32.
Kannegiesser M and Günther H-O (2011). An integrated optimization model for managing the global value chain of a chemical commodities manufacturer. Journal of the Operational Research Society 62 (4): 711–721.
Kaushik A (2008). Offshore Outsourcing: Quantifying ROI, CIO Magazine, 4 November.
Kellerer H and Pferschy U (2004). Improved dynamic programming in connection with an FPTAS for the knapsack problem. Journal of Combinatorial Optimization 8 (1): 5–11.
Kellerer H, Pferschy U and Pisinger D (2004). Knapsack Problems. Springer-Verlag: Berlin/Heidelberg: p 16.
Korte B and Vyen J (2006). Combinatorial Optimization Theory and Algorithms, 3rd edn. (Chapter 5) Springer: Germany.
Leach PT (2012). Logistics challenges force shippers to think outside the box. The Journal of Commerce. 7 May, http://www.joc.com/portsterminals/outside-box, accessed 8 August 2012.
Lei L, Zhong H and Chaovalitwongse WA (2009). On the integrated production and distribution problem with bidirectional flows. INFORMS Journal on Computing 21 (4): 585–598.
Martello S, Pisinger D and Toth P (1999). Dynamic programming and strong bounds for the 0–1 knapsack problem. Management Science 45 (3): 414–424.
McKinsey (2010). McKinsey Global Survey Results: The challenges ahead for supply chains, McKinsey Quarterly November, http://www.mckinseyquarterly.com/The_challenges_ahead_for_supply_chains_McKinsey_Global_Survey_results_2706, accessed 8 August 2012.
Wang G and Lei L (2012). Polynomial-time solvable cases of the capacitated multi-echelon shipping network scheduling problem with delivery deadlines. International Journal of Production Economics 2 (137): 263–271.
Yan SY, Juang DS, Chen CR and Lai WS (2005). Global and local search algorithms for concave cost transshipment problems. Journal of Global Optimization 33 (1): 123–156.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wang, G., Lei, L. & Lee, K. Supply chain scheduling with receiving deadlines and non-linear penalty. J Oper Res Soc 66, 380–391 (2015). https://doi.org/10.1057/jors.2014.2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2014.2