Zagadnienie przepływowe z ograniczeniami "bez magazynowania". Algorytm tabu search z multiruchami

• Autorzy: Grabowski J. , Pempera J.

Warianty tytułu

EN

Flow shop with no store constraints. Algorithm TS with multimoves

• Języki publikacji: PL

Abstrakty

PL

Dla zagadnienia przepływowego z ograniczeniami "bez magazynowania" przedstawiono w pracy model grafowy, własności problemu oraz algorytm oparty na technice tabu search. W proponowanym algorytmie wykorzystano idee bloków zadań oraz zastosowano całkowicie nowe pojęcie nazywane multiruchem. Wysoką skuteczność algorytmu potwierdzają wyniki badań eksperymentalnych dokonane na literaturowych danych testowych, w których aż dla 96 instancji spośród 120 uzyskano nowe rozwiązania referencyjne.

EN

The paper deal with flow-shop scheduling problem with no store constrains and the makespan criterion. Some properties, models of the problem and algorithm based on the taboo search method have been presented and discussed. In the proposed algorithm, the blocks of jobs ideas and new mechanism called multimove are used. The high efficiency of proposed mechanism confirm the results of the computation experiment, where for 96 over 120 instances are obtained new references solution.

Słowa kluczowe

PL

problem przepływowy; ograniczenie bez magazynowania; algorytm tabu search

EN

flow shop problem; no store constraints; tabu search algorithm

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2005
• Tom: T. 9, z. 1-2
• Strony: 95--104
• Opis fizyczny: Bibliogr. 17 poz., tab.

Twórcy

autor

Grabowski J.

• Instytut Cybernetyki Technicznej Politechniki Wrocławskiej

autor

Pempera J.

• Instytut Cybernetyki Technicznej Politechniki Wrocławskiej

Bibliografia

• [1] Gilmore P.C., Gomory R.E.: Sequencing a state-variable machine: a solvable case of the traveling salesman problem. Operations Research, 12, 1964, 655–679
• [2] Abadi I.N.K., Hall N.G., Sriskandarayah C.: Minimizing Cycle Time in a Blocking Flowshop. Operations Research, 48, 2000, 177–180
• [3] Caraffa V., Ianes S., Bagchi T.P., Sriskandarayah C.: Minimizing makespan in a blocking flowshop using genetic algorithms. International Journal of Production Economics, 70, 2001, 101–115
• [4] Grabowski J., Pempera J.: Sequencing of jobs in some production system. European Journal of Operational Research, 125, 2000, 535–550
• [5] Leistein R.: Flowshop sequencing with limited buffer storage. International Journal of Production Research, 28, 1990, 2085–2100
• [6] McCormick M.L., Pinedo M.L., Shenker S., Wolf B.: Sequencing in an assembly line with blocking to minimize cycle time . Operations Research, 37, 1989, 925–935
• [7] Nowicki E.: The permutation flow shop with buffers: A tabu search approach. European Journal of Operational Research, 116, 1999, 205–219
• [8] Reddi S.S., Ramamoorthy C.V.: On flowshop sequencing problems with no-wait in process. Operational Research Quarterly, 23, 1972, 323–33
• [9] Ronconi D.P.: A note on constructive heuristics for the flowshop problem with blocking. International Journal of Production Economics, 87, 2004, 39–48
• [10] Ronconi D.P.: A branch-and-bound algorithm to mnimize the makespan in a flowshop problem with blocking . Annals of Operations Research (in print)
• [11] Ronconi D.P., Armentano V.A.: Lower bounding schemes for flowshops with blocking in-process. Journal of the Operational Research Society, 52, 2001, 128912–97
• [12] Smutnicki C.: Some properties of scheduling problem with storing constraints. Zeszyty Naukowe AGH: Automatyka, 34, 1983, 223–232
• [13] Hall N.G., Sriskandarayah C.: A survey of machine scheduling problems with blocking and no-wait in process. Operations Research, 44, 1996, 510–525
• [14] Grabowski J., Wodecki M.: A very fast tabu search algorithm for the job shop problem . In: C. Rego, B. Alidaee (Eds), Metaheuristic Optimization v ia Memory and Evolution; Tabu Search and Scatter Search, Kluwer Academic Publishers, 2004, (w druku)
• [15] Grabowski J., Wodecki M.: A very fast tabu search algorithm for the flow shop problem with makespan criterion. Computers and Operations Research, 11, 2004, 1891–1909
• [16] Taillard E.: Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 1993, 278–285
• [17] Nawaz M., Enscore E., Ham I.: A Heuristic algorithm for the m-machine, n-job flowshop sequencing problem. OMEGA The International Journal of Management Science, 11, 1983, 91–95