This paper discusses a capacitated time minimization transportation problem in which transportation operation takes place in two stages. In the first stage, due to some constraints, only a specified flow is transported from available sources to various destinations and in the second stage, a flow is transported depending upon the total demand of the destinations. The current problem is motivated by a production system of a steel industry where semi-finished jobs, initially located at various bins in its warehouse, are transported to various manufacturing facilities by transporters for the final processing and finishing. Due to some additional constraints, it is not possible to transport the number of semi-finished jobs equal to the exact number of final products to be manufactured, in one go. Therefore the transportation operation has to take place in two stages. Further, a capacity is associated with each bin-machine link which makes the current problem, a capacitated, two stage time minimization transportation problem with restricted flow. The objective is to minimize the sum of the transportation times for Stage-I and Stage-II. A polynomial time iterative algorithm is proposed that within each iteration, solves a restricted version of a related standard capacitated time minimization transportation problem and generates a pair of Stage-I and Stage-II times with Stage-II time strictly less than the Stage-II time of the previous iteration, whereas Stage-I time may increase. Out of these generated pairs, a pair with the minimum sum of transportation times of Stage-I and Stage-II is selected that gives the global optimal solution. Numerical illustration is included in the support of the theory.
Accepté le :
DOI : 10.1051/ro/2016033
Mots-clés : Non-convex programming, combinatorial optimization, time transportation problem, capacitated transportation problem, flow constraint
@article{RO_2017__51_2_447_0, author = {Kaur, Prabhjot and Verma, Vanita and Dahiya, Kalpana}, title = {Capacitated two-stage time minimization transportation problem with restricted flow}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {447--467}, publisher = {EDP-Sciences}, volume = {51}, number = {2}, year = {2017}, doi = {10.1051/ro/2016033}, mrnumber = {3657434}, zbl = {1365.90217}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro/2016033/} }
TY - JOUR AU - Kaur, Prabhjot AU - Verma, Vanita AU - Dahiya, Kalpana TI - Capacitated two-stage time minimization transportation problem with restricted flow JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2017 SP - 447 EP - 467 VL - 51 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2016033/ DO - 10.1051/ro/2016033 LA - en ID - RO_2017__51_2_447_0 ER -
%0 Journal Article %A Kaur, Prabhjot %A Verma, Vanita %A Dahiya, Kalpana %T Capacitated two-stage time minimization transportation problem with restricted flow %J RAIRO - Operations Research - Recherche Opérationnelle %D 2017 %P 447-467 %V 51 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2016033/ %R 10.1051/ro/2016033 %G en %F RO_2017__51_2_447_0
Kaur, Prabhjot; Verma, Vanita; Dahiya, Kalpana. Capacitated two-stage time minimization transportation problem with restricted flow. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 2, pp. 447-467. doi : 10.1051/ro/2016033. http://www.numdam.org/articles/10.1051/ro/2016033/
The scaling network simplex algorithm. Oper. Res. 40 (1992) 5–13. | DOI | MR | Zbl
and ,The transportation problem and its variants. J. Oper. Res. Soc. 24 (1973) 79–99. | DOI | MR | Zbl
,A new strongly polynomial dual network simplex algorithm. Math. Program. 78 (1997) 131–148. | DOI | MR | Zbl
and ,On lexicographic optimal solutions in transportation problem. Optimization 39 (1997) 383–403. | DOI | MR | Zbl
and ,On a standard time transportation problem. ASOR Bulletin 20 (2001) 2–14.
and ,A Variant of Transportation problem in which the constraints are of Mixed Type. Oper. Res. Quarterly 25 (1974) 437–445. | DOI | MR | Zbl
,A min-max problem. ZOR 24 (1980) 191–200. | MR | Zbl
and ,C. Berge, Theory of Graphs and its Applications. Dunod, Paris (1958).
A procedure for time minimizing transportation problem. Indian J. Pure Appl. Math. 8 (1977) 920–929. | MR | Zbl
, and ,G.B. Dantzig, Linear Programming and Extensions. Princeton University Press, Princeton (1963). | MR | Zbl
G.B. Danzing and M. Thapa, Linear programming: Theory and extensions. Springer Verlag, New York, Berlin (1963). | MR
Capacitated transportation problem with bounds on rim conditions.Eur. J. Oper. Res. 178 (2007) 718–737. | DOI | MR | Zbl
and ,Time minimization transportation problem. Naval Res. Logist. Quart. 18 (1969) 345–357. | DOI | MR | Zbl
,On a class of capacitated transportation problem. Manage. Sci. 5 (1959) 304–318. | DOI | MR | Zbl
,The distribution of a product from several sources to numerous localities. J. Math. Phys. 20 (1941) 224–230. | DOI | JFM | MR | Zbl
,Two stage fuzzy transportation problem.J. Phys. Sci. 10 (2006) 63–69.
,The bottleneck transportation problem. Naval Res. Logist. Quart. 18 (1971) 465–472. | DOI | MR | Zbl
and ,Two-Stage interval time minimization transportation problem with capacity constraints. Innovative Syst. Designs 6 (2015) 79–85.
and ,S. Khanna, H.C. Bakshi and M.C. Puri, On controlling total flow in transportation problems. In: Scientific Management of Transport Systems. North Holland, The Neitherlands (1981) 293–301. | MR | Zbl
Solving a Transportation problem with Mixed Constraints and a Specified Transportation Flow. Opsearch 20 (1983) 16–24. | MR | Zbl
, and ,The Transportation problem with Mixed Constraints. Oper. Res. Quarterly 25 (1974) 447–455. | DOI | MR | Zbl
and ,K.G. Murty, Linear and Combinatorial Programming. John Wiley and Sons, Inc., New York (1976). | MR | Zbl
A polynomial time primal network simplex algorithm for minimum cost flows. Math. Program. 78 (1997) 109–129. | DOI | MR | Zbl
,On minimizing the duration of transportation. Proc. Indian Acad. Sci. 91 (1982) 53–57. | DOI | Zbl
,Solving two stage transportation problem.Commun. Comput. Inf. Sci. 140 (2011) 159–165. | Zbl
and ,A note on two stage interval time minimization transportation problem. ASOR Bulletin 27 (2008) 12–18.
, and ,An iterative algorithm for two level hierarchical time minimization transportation problem. Eur. J. Oper. Res. 246 (2015) 700–707. | DOI | MR | Zbl
, , and ,Capacitated two stage transportation problem. Asia Pacific J. Oper. Res. 27 (2010) 457–476. | DOI | MR | Zbl
, and ,A different approach for solving two stage fuzzy transportation problem.Int. J. Contemp. Math. Sci. 6 (2011) 517–526. | MR | Zbl
, ,Some remarks on time transportation problem. Naval Res. Logist. Quart. 18 (1971) 465–472. | DOI | MR | Zbl
,Cité par Sources :