Polynomial-time solvable cases of the capacitated multi-echelon shipping network scheduling problem with delivery deadlines
International Journal of Production EconomicsPublished 13 February 2012
Gang Wang, Lei Lei
Citations28
SJR quartileQ1
SJR score2.83
SNIP2.67
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Three polynomial-time solvable cases of the problem of operations scheduling for a capacitated multi-echelon shipping network with delivery deadlines with identical order quantities, designated suppliers, and divisible customer order sizes are reported.
Abstract
We consider the problem of operations scheduling for a capacitated multi-echelon shipping network with delivery deadlines. Over the network, semi-finished goods are shipped from origins to many demand points through a capacitated network consisting of shipping links and capacitated processing centers. The shipping operations are performed by a fleet of transporters which require time to travel from one location to another. Each demand point has a specified shipment quantity and a deadline for delivery. The problem is to find a feasible operation schedule to minimize the shipping and penalty cost. This problem is a computationally difficult one because of its inherent combinatorial nature. We report three polynomial-time solvable cases of this problem with (a) identical order quantities; (b) designated suppliers; and (c) divisible customer order sizes. These results reveal some interesting properties of the problem, and can be used to facilitate the design of fast heuristics for operations scheduling of capacitated shipping networks.
Keywords
Engineering
Combinatorial Optimization: Theory and Algorithms
1,188 Citations2012Bernhard Körte, Jens Vygen
International Journal of Production EconomicsAn optimization approach for managing fresh food quality throughout the supply chain
626 Citations2009Aiying Rong, Renzo Akkerman +1 more
Transportation ScienceSynchronized Development of Production, Inventory, and Distribution Schedules
255 Citations1999Francesca Fumero, Carlo Vercellis
An integrated optimization model for production and distribution planning is proposed, with the aim of optimally coordinating important and interrelated logistic decisions such as capacity management, inventory allocation, and vehicle routing.
European Journal of Operational ResearchMachine scheduling with job delivery coordination
235 Citations2003Yung-Chia Chang, Chung-Yee Lee
A proof of NP-hardness and a heuristic with worst-case analysis is provided for the problem in which jobs are processed on a single machine and delivered by a single vehicle to one customer area and another heuristic is provided that is 100% error bound.
IIE TransactionsOn the integrated production, inventory, and distribution routing problem
204 Citations2006Lei Lei, Shuguang Liu +2 more
Operations ResearchOrder Assignment and Scheduling in a Supply Chain
203 Citations2006Zhi‐Long Chen, Guruprasad Pundoor
This work considers the supply chain of a manufacturer who produces time-sensitive products that have a large variety, a short life cycle, and are sold in a very short selling season and proposes several fast heuristics for the intractable problems.
International Journal of Production EconomicsAn integrated production-inventory model with imperfect production processes and Weibull distribution deterioration under inflation
190 Citations2006Sh-Tyan Lo, Hui‐Ming Wee +1 more
INFORMS journal on computingThe Integrated Production and Transportation Scheduling Problem for a Product with a Short Lifespan
173 Citations2007H. Neil Geismar, Gilbert Laporte +2 more
This study considers a variation of PTSP that involves a short shelf life product; hence, there is no inventory of the product in process, and develops lower bounds on the optimal solution, and proposes a two-phase heuristic based on the analysis.
Journal of SchedulingThe integrated production–inventory–distribution–routing problem
167 Citations2008Jonathan F. Bard, Narameth Nananukul
A model is presented that includes a single production facility, a set of customers with time varying demand, a finite planning horizon, and a fleet of vehicles for making the deliveries and uses an allocation model in the form of a mixed integer program to find good feasible solutions that serve as starting points for the tabu search.
International Journal of Production EconomicsAn integrated production–distribution model for the dynamic location and allocation problem with safety stock optimization
153 Citations2009Elisa Gebennini, Rita Gamberini +1 more
An original model for the dynamic location-allocation problem with control of customer service level and safety stock optimization is presented and an industrial application is illustrated demonstrating the effectiveness of the proposed optimization approach.
International Journal of Production EconomicsCoordinated supply chain scheduling
130 Citations2009Tadeusz Sawik
A mixed integer programming approach is proposed for a long-term, integrated scheduling of material manufacturing, material supply and product assembly in a customer driven supply chain in the electronics industry.
International Journal of Production EconomicsAn integrated location, production, distribution and investment model for a multinational corporation
119 Citations2003M. Khurrum S. Bhutta, Faizul Huq +2 more
International Journal of Production EconomicsAn integrated production–distribution model for a deteriorating inventory item
110 Citations2010Changyuan Yan, Avijit Banerjee +1 more
This work develops an integrated production-distribution model for a deteriorating item in a two-echelon supply chain and outlines a procedure for determining the optimal supply chain decisions with the objective of minimizing the total system cost.
Choice Reviews OnlineOptimization: foundations and applications
110 Citations2000
This paper presents a meta-modelling procedure called "Constrained Maximization and Minimization of Linear Equations", which automates the very labor-intensive and therefore time-heavy process of solving nonlinear Equations problems.
Annals of Operations ResearchThe Coordination of Scheduling and Batch Deliveries
101 Citations2005Nicholas G. Hall, Chris N. Potts
This paper considers several scheduling problems where deliveries are made in batches with each batch delivered to the customer in a single shipment to provide efficient algorithms that minimize total cost or show that the problem is intractable.
Management ScienceDynamic Economic Lot Size Model with Perishable Inventory
101 Citations2000Vernon Ning Hsu
Journal of ComplexityBin packing with divisible item sizes
101 Citations1987E. G. Coffman, M. R. Garey +1 more
It is shown that First Fit Decreasing produces optimal packings under this restriction, and that if in addition the largest item size divides the bin capacity, then even the less powerful First Fit algorithm is optimal.
Mathematical ProgrammingA strongly polynomial algorithm for the transportation problem
67 Citations1995Peter Kleinschmidt, Heinz Schannath
An algorithm which runs in time proportional tom logm(k + n logn) (assuming w.l.o.g.m⩾n) is described, which is a slight improvement over the bound achieved by an application of a min-cost-flow algorithm of Orlin to the transportation problem.
Naval Research Logistics (NRL)Production and transport logistics scheduling with two transport mode choices
62 Citations2005Haiyan Wang, Chung‐Yee Lee
This paper considers a new class of scheduling problems arising in logistics systems in which two different transportation modes are available at the stage of product delivery, and provides a branch and bound algorithm with two different lower bounds that is more efficient than CPLEX.
International Journal of Production EconomicsJoint cyclic production and delivery scheduling in a two-stage supply chain
53 Citations2009Guruprasad Pundoor, Zhi‐Long Chen
Various managerial insights based on an extensive set of computational tests are reported, including how the value of warehouse and the delivery frequency from the suppliers to the warehouse are influenced by various problem parameters including production rates of the suppliers, unit inventory costs, delivery costs, and the warehouse location.
International Journal of Production EconomicsA simulation/metaheuristic approach to newspaper production and distribution supply chain problems
53 Citations2009Wen‐Chyuan Chiang, Robert A. Russell +2 more
This paper examines two-level and three-level supply chains for a midsize US newspaper in the Midwest that delivers to households and businesses in over 200 zip codes that span across various states and uses simulation to evaluate the performance of the proposed solution.
Annals of Operations ResearchDGAP - The Dynamic Generalized Assignment Problem
28 Citations1997Konstantin Kogan, Avraham Shtub
The continuous-time op-timal control model of the Generalized Assignment Problem is formulated, where identical tasks are grouped into jobs, each job is performed by each agent with a fixed (production) rate, while due dates are transformed into demand.
PolyPublie (École Polytechnique de Montréal)Distributed Operations Planning in the Lumber Supply Chain: Models and Coordination
24 Citations2009Jonathan Gaudreault, Pascal Forget +4 more
International Journal of Production EconomicsA network approach to modeling the multi-echelon spare-part inventory system with backorders and interval-valued demand
22 Citations2011Eugene Levner, Yael Perlman +2 more
Information Processing LettersA polynomial algorithm for the multiple knapsack problem with divisible item sizes
18 Citations2009Paolo Detti
A polynomial algorithm for the multiple bounded knapsack problem with divisible item sizes is presented and it is shown that the algorithm complexity reduces to O(nlogn+nm) when a single copy exists of each item.