Унапређење конструктивних хеуристика за проблеме комбинаторне оптимизације у операционом менаџменту

Abstract

Операциони менаџер користи скуп поступака чији је циљ да се послови ураде брже, јефтиније и квалитетније. Научници из области операционог менаџмента имају задатак да ови поступци буду изводљиви и практични. Скоро увек, менаџери покушавају да нешто оптимизују – или је то минимизација трошкова и потрошње енергије, или пак, максимизација профита, резултата, перформанси и ефикасности. Међутим, није увек могуће пронаћи оптимална решења. У пракси, менаџер мора да се задовољи решењима која можда нису оптимална, али су допустива, задовољавајућа, робустна, и достижна у разумном времену. Оваква решења се добијају применама хеуристика, које могу бити конструктивне, побољшавајуће или хибридне. Област истраживања у докторској дисертацији су конструктивне хеуристике за проблеме комбинаторне оптимизације у операционом менаџменту који припадају класи сложености НП. Представљен је нови генерализовани конструктивни алгоритам који омогућава да се разноврсне хеуристике формирају избором његових аргумената. Такође је уведено опште окружење за генерисање пермутација, које формира везу између енумерације пермутација и корака у конструктивним хеуристикама уметања. Предложен је скуп аргумената генерализованог алгоритма који омогућује паралелно праћење више парцијалних решења за време извршавања алгоритма. Могућности и предности генерализованог алгоритма су представљене кроз његову примену на проблем формирања ћелија у производним системима, проблем распореда производних ћелија и проблем редоследа послова у линији. Нови приступ даје решења која на испитиваним примерима надмашују најбоље познате резултате из литературе.

Operations manager deals with a collection of methods for getting things done more quickly, more cheaply or to a higher standard of quality. It is the job of the management scientist to make sure that these methods are practical and relevant. Almost always managers try to optimize something - whether to minimize the cost and energy consumption, or to maximize the profit, output, performance and efficiency. Subsequently, it is not always possible to find the optimal solutions. In practice, managers have to settle for suboptimal solutions or even feasible ones that are satisfactory, robust, and practically achievable in a reasonable time scale. These kind of solutions are obtained with heuristics, which can be constructive, improvement heuristics or hybrid. The field of research in the doctoral thesis are constructive heuristics for NP-hard combinatorial optimization problems in operations management. A new generalized constructive algorithm is presented which makes it possible to select a wide variety of heuristics just by the selection of its arguments values. A general framework for generating permutations of integers is presented. This framework forms a link between the numbering of permutations and steps in the insertion-based heuristics. A number of arguments controlling the operation of the generalized algorithm tracking multiple partial solutions, are identified. Features and benefits of the generalized algorithm are presented through the implemetations to the Cell Formation Problem, the Quadratic Assignment Problem and the Permutation Flowshop Problem. The new approach produces solutions that outperform, on the tested instances, the best known results from literature.