Hybrydowy algorytm tabu dla niepermutacyjnego problemu przepływowego z kryterium sumacyjnym

• Autorzy: Grabowski J. , Pempera J.

Warianty tytułu

EN

A hybrid tabu search algorithm for the non-permutation flow shop problem

• Języki publikacji: PL

Abstrakty

PL

Praca poświęcona jest niepermutacyjnemu problemowi przepływowemu z kryterium sumy terminów zakończenia realizacji zadań. W pracy przedstawiono opis matematyczny problemu, model grafowy oraz pewne własności problemu, które pozwalają na wyeliminowanie znacznej frakcji ruchów typu zamień sąsiednie nie lepszych od rozwiązania bazowego. Skonstruowano hybrydowy algorytm przeszukiwania z zabronieniami oparty na otoczeniu generowanym przez tego typu ruchy. Przeprowadzono badania eksperymentalne algorytmu na literaturowych danych testowych Tailarda.

EN

The paper deals with non-permutation flow shop with total completion time criterion. In the paper the mathematical model and graph model is presented. Some properties of the problem associated with the block theory have been presented and discussed. These properties allow us to significantly reduce neighbourhoods which are based on the adjacent interchange type. To validate efficiency of the discussed neighbourhoods, the hybrid tabu search algorithm have been developed and executed on a well-known Tailard's benchmarks.

Słowa kluczowe

PL

problem przepływowy; kryterium sumacyjne; tabu search

EN

non-permutation flow shop problem; total completion time; tabu search

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2009
• Tom: T. 13, z. 2
• Strony: 289--296
• Opis fizyczny: Bibliogr. 14 poz., tab.

Twórcy

autor

Grabowski J.

• Instytut Automatyki, Informatyki i Robotyki, Politechnika Wrocławska

autor

Pempera J.

• Instytut Automatyki, Informatyki i Robotyki, Politechnika Wrocławska

Bibliografia

• [1] Gupta J.N.D., Stafford S., Flowshop scheduling research after five decades. European Journal of Operational Research, 169, 2006, 699-711.
• [2] Bansal S.P., Minimizing the sum of completion times of n-jobs over m-machines in a flowshop - a branch and bound approach. AIIE Transactions, 9, 1977, 306-311.
• [3] Allahverdi A., Aldowaisan Т., New heuristics to minimize total completion time in m-machine flowshops. International Journal of Production Economics, 77, 2002, 71-83.
• [4] Rajendran C, Ziegler H., Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155, 2004, 426-138.
• [5] Reeves C.R., Yamada Т., Genetic algorithms, path relinking and the flowshop sequencing problem. Evolutionary Computation, 6, 1998, 45-60.
• [6] Tasgetiren M.F., Liang Y., Sevkli M., Gencyilmaz G., A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research, 177, 2007, 1930-1947.
• [7] Bożejko W., Pempera J., Smutnicki A., Parallelization of metaheuristics for the flow shop scheduling problem. Lecture Notes in Computer Science (w druku).
• [8] Tandon M., Cummings P.T., Levan M.D., Flowshop sequencing with non-permutation schedules. Computers and Chemical Engineering, 15, 1991, 601-607.
• [9] Lin S.W., Ying K.C., Applying a hybrid simulated annealing and tabu search approach to non-permutation flowshop scheduling problems. International Journal of Production Research, 45, 5, 2009, 1411-1424.
• [10] Grabowski J., Nowicki E., Smutnicki C, Metoda blokowa w zagadnieniach szeregowania zadań. EXIT, Warszawa 2003.
• [11] Nowicki E., Smutnicki C, A fast taboo search algorithm for job shop problem. Management Science, 42,6, 1996, 797-813.
• [12] Watson J.P., Howe A.E., Whitley L.D., Deconstruction Nowicki and Smutnicki's i-TSAB algorithm for the job shop problem. Computers and Operations Research, 33,9, 2006, 2623-2644.
• [13] Taillard E., Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 1993, 278-285.
• [14] Nawaz E., Enscore E.E., Ham I., A heuristic algorithm for the m—machine, n—job flow—shop sequencing problem. Omega International Journal of Management Science, 11, 1993, 91-95.