Geodesic
Two Schemes of the Branch and Bound Method for a Flow Shop Total Weighted Tardiness Minimization Problem
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 154 (2012) no. 3, pp. 180-189 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Two schemes of the branch and bound method for a flow shop total weighted tardiness minimization problem are suggested in this paper. The first scheme consists in the construction of the schedule in the common order (at the beginning the first work in the schedule is chosen, then the second work, etc.) and the second scheme presupposes the construction of the schedule in the inverse order (at the beginning the last work in the schedule is chosen, then the penultimate work, etc.). It is shown by numerical experiments that the efficiency of the methods strongly depends on the problem's parameters, which can be easily calculated from the initial data. Criteria for choosing the most efficient method for any particular problem are proposed.
Keywords: flow shop, branch and bound method, total weighted tardiness minimization. 
@article{UZKU_2012_154_3_a16,
     author = {I. K. Agapeevich and V. R. Fazylov},
     title = {Two {Schemes} of the {Branch} and {Bound} {Method} for a {Flow} {Shop} {Total} {Weighted} {Tardiness} {Minimization} {Problem}},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {180--189},
     year = {2012},
     volume = {154},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2012_154_3_a16/}
}
TY  - JOUR
AU  - I. K. Agapeevich
AU  - V. R. Fazylov
TI  - Two Schemes of the Branch and Bound Method for a Flow Shop Total Weighted Tardiness Minimization Problem
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2012
SP  - 180
EP  - 189
VL  - 154
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2012_154_3_a16/
LA  - ru
ID  - UZKU_2012_154_3_a16
ER  - 
%0 Journal Article
%A I. K. Agapeevich
%A V. R. Fazylov
%T Two Schemes of the Branch and Bound Method for a Flow Shop Total Weighted Tardiness Minimization Problem
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2012
%P 180-189
%V 154
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2012_154_3_a16/
%G ru
%F UZKU_2012_154_3_a16
I. K. Agapeevich; V. R. Fazylov. Two Schemes of the Branch and Bound Method for a Flow Shop Total Weighted Tardiness Minimization Problem. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 154 (2012) no. 3, pp. 180-189. http://geodesic.mathdoc.fr/item/UZKU_2012_154_3_a16/

[1] Baker K. R., Introduction to sequencing and scheduling, Wiley, N. Y., 1974, 305 pp.

[2] Bozejko W., Uchronski M., Wodecki M., “Scatter search for a weighted tardiness flow shop problem”, MISTA 2009, Multidisciplinary Int. Scheduling Conf. (Dublin, Ireland, 10–12 August 2009) http://staff.iiar.pwr.wroc.pl/wojciech.bozejko/papers/2009/MISTA 4pages.pdf

[3] Bozejko W., Wodecki M., “Population-Based Heuristics for Hard Permutational Optimization Problems”, Int. J. Comput. Intell. Res., 2:2 (2006), 151–158 | MR

[4] Bulbul K., Kaminsky Ph., Yano C., “Flow Shop Scheduling with Earliness, Tardiness, and Intermediate Inventory Holding Costs”, Nav. Res. Logist., 51:3 (2004), 407–445 | DOI | MR | Zbl

[5] Cicirello V. A., “On the Design of an Adaptive Simulated Annealing Algorithm”, First Workshop on Autonomous Search (Rhode Island, USA, 23 September 2007) http://www.forevermar.com/SimA.pdf

[6] Rahimi-Vahed A. R., Mirghorbani S. M., “A multi-objective particle swarm for a flow shop scheduling problem”, J. Combin. Optim., 13:1 (2007), 79–102 | DOI | MR | Zbl

[7] Sen T., Sulek J. M., Dileepan P., “Static scheduling research to minimize total weighted and unweighted tardiness: A state-of-the-art survey”, Int. J. Prod. Econ., 3:1 (2003), 1–12 | DOI

[8] Lenstra J. K., Rinnooy Kan A. H. G., “Complexity results for scheduling chains on a single machine”, Eur. J. Oper. Res., 96 (1980), 270–275 | DOI | MR

[9] Engin O., Doyen A., “A new approach to solve flowshop scheduling problems by artificial immune systems”, Future Gener. Comp. Sy., 20:6 (2004), 1083–1095 | DOI

[10] Agapeevich I. K., Fazylov V. R., “Generator iskhodnykh dannykh dlya zadachi minimizatsii summarnogo vzveshennogo zapazdyvaniya v konveiernykh sistemakh”, Issled. po priklad. matem. i informat., 27, Izd-vo Kazan. un-ta, Kazan, 2011, 3–7

[11] Konvei R. V., Maksvell V. L., Miller L. V., Teoriya raspisanii, Nauka, M., 1975, 359 pp. | MR

[12] Ignall E., Shrage L., “Application of the Branch-and-Bound Technique to Some Flow-Shop Scheduling Problems”, Oper. Res., 13:3 (1965), 400–412 | DOI | MR

[13] Fazylov V. R., Zadacha manipulyatora galvanicheskoi linii, Kazan. matem. o-vo, Kazan, 2000, 79 pp.