Analiza primene pravila prioriteta na problemu raspoređivanja u fleksibilno protočnoj proizvodnji

Abstract

U ovom radu analizirana je grupa jednostavnih heurističkih metoda koje se koriste u rešavanju problema raspoređivanja u proizvodnji i pružanju usluga. Analiza je izvršena na primeru raspoređivanja u fleksibilno-protočnoj proizvodnji koji je poznat po engleskom akronimu FFS (Flexible- Flow Shop). Zadatak je odrediti raspored obrade više proizvoda na više mašina, pri čemu svi proizvodi slede isti redosled obrade i za svaku obradu postoji na raspolaganju više mašina. Za opisani problem FFS dat je odgovarajući matematički model mešovitog celobrojnog programiranja. Od potencijalnih metoda za rešavanje postavljenog zadatka detaljnije se razmatraju jednostavne heuristike jer je originalni zadatak NP tvrd i nalaženje tačnog optimalnog rešenja zahtevalo bi neprihvatljivo dugo računarsko vreme. Heurističke metode počivaju na pravilima prioriteta koja se izvode na osnovu relacija važnosti izmenu proizvoda i trajanja njihovih obrada na pojedinačnim mašinama. Heurističke metode imaju široku primenu u rešavanju praktičnih problema i to je bila motivacija za analizu čiji se rezultati saopštavaju u ovom radu. Cilj analize je da se na jednom hipotetičkom primeru problema raspoređivanja odrede ona pravila prioriteta koja daju dobra rešenja pri čemu se ocenjivanje obavlja korišćenjem različitih kriterijumskih funkcija. Analiza je obavljena pomoću računarskog programa LEKIN. Kao glavni rezultat analize pokazano je da pravila prioriteta daju različita rešenja za problem FFS i da svako od tih rešenja predstavlja značajno dobar rezultat sa aspekta neke od razmatranih kriterijumskih funkcija.

In this paper we analyzed a group of simple heuristic methods, which are used for solving the scheduling problem in manufacturing and services. The analysis was performed on the scheduling problem in a flexible-flow shop production, which is known by the English term - Flexible-Flow Shop (FFS). The task is to determine the schedule of processing multiple products on multiple machines, where all the products have the same sequence of processing and for each process there are multiple machines available. For this FFS problem we present the corresponding mathematical model of mixed integer programming. Among potential methods for solving the set task, we consider simple heuristics because the original scheduling problem is NP-hard and finding the exact optimal solution would require unacceptably long computing time. Heuristic methods are based on priority rules that are performed based on the relations of importance between products and their processing time on individual machines. Heuristic methods are widely used for solving practical problems, which was the motivation for the analysis performed in this paper. The aim of the analysis is to identify those priority rules, from a set of considered, which provide a good solution to a hypothetical scheduling problem example, where the evaluation of solution is performed using different criteria functions. The analysis that is presented in the paper was obtained by using the computer program LEKIN. The main results of the analysis indicated that priority rules give different solutions to the problem of FFS and that each of these solutions is a significantly good result in terms of some of the considered criteria functions.