Seminars are offered to students for education in various disciplines. The seminars may be limited in terms of the maximum number of participants, e.g., to have lively interactions. Due to capacity limitations, those seminars are often offered several times to serve the students’ demands. Still, some seminars are more popular than others and it may not be possible to grant access to all interested students due to capacity limitations. In this paper, a simple, but efficient random selection using key objectives (SEKO) assignment strategy is proposed which achieves the following goals: (i) efficiency by utilizing all available seminar places, (ii) satisfying all students by trying to assign at least one seminar to each student, and (iii) fairness by considering the number of assigned seminars per student. We formulate various theoretical optimization models using integer linear programming (ILP) and compare their solutions to the SEKO assignment based on a real-world data set. The real-world data set is also used as the basis for generating large data sets to investigate the scalability in terms of demand and number of seminars. Furthermore, the first-in first-out (FIFO) assignment, as a typical implementation of fair assignments in practice, is compared to SEKO in terms of utilization and fairness. The results show that the FIFO assignment suffers in realworld situations regarding fairness, while the SEKO assignment is close to the optimum and scales regarding computational time in contrast to the ILP.
Aquaculture is an important industry in certain coastal areas. Focusing on farming of salmon and trout, an operational planning problem arises with the goal of allocating supply of fish to demand expressed through customer orders. This paper provides a conceptual model of such a planning problem, defines a corresponding bi-objective mathematical programming model. The problem is novel with respect to the structure of the transportation of fish, and the rules for satisfying customer orders with respect to fish size, quality, certification, and health status. Computational experiments are conducted to gain further insights into the use of the provided model to provide support for planners involved in the operational decision making. Results indicate that the bi-objective optimization model can be useful in situations where supply is insufficient to cover all the demand within a given planning horizon.
Periodic routing and scheduling is of utmost importance in many industries with mobile personnel working in the field: sales representatives, service technicians, suppliers, etc. The resulting optimization problems are of large scale and complexity, mostly due to discrete, combinatorial nature of the systems and due to complicated, nonuniform constraints. In many cases the long-term stability of the customer to personnel allocation is required, leading to the decomposition of the major problem into single employee subproblems. The paper deals with building clusters of customers visited by a single salesperson. The procedure takes into account diverse system requirements and constraints, possible traveling schedules and expected operational costs. The difficulty of the problem lies in its large scale and constraints complexity as well as in troublesome objective evaluation for the given solution. The general solution concept is presented. Its usefulness is supported by the results of the computational experiments.
W artykule opisane jest zagadnienie przydziału pracowników do stanowisk pracy w systemie odpraw celnych. Ze względu na specyfikę problemu, w związku z występowaniem ryzyka zachowań korupcyjnych, obsada stanowisk pracy powinna być generowana w sposób losowy. Zalecane jest także uwzględnienie rotacji stanowisk dla pracowników, którzy np. zbyt często pełnili służbę w uciążliwym miejscu pracy. Sformułowany jest model matematyczny dla tego zagadnienia. Następnie zaprezentowany jest proponowany szybki algorytm znajdujący rozwiązanie dedykowane dla zdefiniowanego problemu.
EN
The article discusses the assignment problem of employees to workplaces in the customs clearance system. Due to the specific nature of the problem, due to the risk of corruption, staffing should be generated randomly. It isalsoadvisable to includerotation of positions for employeeswho, for example, have too often served in a cumber some workplace. The mathematical model for this problem is formulated. Then the proposed fast algorith mispresented, which is dedicated to the defined problem.
In the era of rapidly changing market and consumer needs, there are dynamic changes in the services offered. This also applies to the car fleet market. Currently, the approach to owning a vehicle is changing to other forms such as rental or subscription. Different types of funding are conducive to changes in the fleet management industry. More and more sophis-ticated services are offered for corporate clients, but also private customers. In the context of these changes, the approach to different aspects of vehicle use is also clarified, including what has been noticeable in recent years, increased interest in road safety, environmental issues and most importantly costs of use and possession of the vehicle. This puts high demands on fleet managers who sustainably need to match the structure of their fleets to the needs and capabilities of their customers while taking into account safety and ecology issues. This is a complicated task that requires decision-making assistance. This article addresses the support of the fleet manager decision, taking into account the sustainable management model. The article aimed to develop a model that takes into account the aspects of safety and ecology from the operator-financier the point of view. The result of the article is to provide a decision-making tool for the selection of vehicles and drivers, taking into account their characteristics to accomplish their tasks. The work presents the problem of fleet management, shows the characteristics of different forms of financing and the impact of market trends on the current approach to these problems. The analysis of safety aspects to the possibility of using different methods affecting its level was then presented. Another element of the article is a mathematical model of the problem of resources assignment for tasks. The developed model is universal and can be used for evaluation and optimisation. To this end, the function of the criterion has been formulated, taking into account the aspects of safety, ecology and financial aspects. It also takes into account the randomness of adverse events and the duration of the remaining appropriations in the out-of-order state. This Model can be used for the risk assessment of the driving staff. The developed model was implemented in the Flexsim environment for a computational example for a trading company. Computational experiments have indicated the correctness of the model and its high application potential, as well as further directions of model development to support complex management processes carried out by fleet managers.
A heuristics based approach to practical solving theoretically intractable combinatory and network problems is discussed. Compound heuristics (heuristics compositions) are suggested to be more efficient procedures for real size problem instances. Some aspects of the heuristics compositions topic are illustrated by optimum permutation problems. We describe a uniform presentation of the chief types of the problems and their interrelations, including the relation “to be a special case of a problem”. We consider a number of algebraic structures and combinatory constructions on permutation sets and present an inclusion chain of these constructions. The chain enables us to establish and clarify many interrelations for the minimum permutation problems, with algorithmic and complexity aspects taken into account. We also concern the applications of some problems as well.
The article presents the problem of the task assignment of the vehicles for the transportation company, which deals with the transport of the cargo in the full truckload system. The presented problem is a complex decision making issue which has not been analysed in the literature before. There must be passed through two stages in order to solve the task assignment problem of the vehicles for the transportation company. The first stage is to designate the tasks, the other one is to determine the number of the vehicles that perform these tasks. The task in the analysed problem is defined as transporting the cargo from the suppliers to the recipients. The transportation routes of the cargo must be determined. In order to solve the task assignment problem of the vehicles, the genetic algorithm has been developed. The construction stages of this algorithm are presented. The algorithm has been developed to solve the multi-criteria decision problem. What is more, the algorithm is verified by the use of the real input data.
Factors contributing to winning games are imperative, as the ultimate objective in a game is victory. The aim of this study was to identify the factors that characterize the game of cricket, and to investigate the factors that truly influence the result of a game using the data collected from the Champions Trophy cricket tournament. According to the results, this cricket tournament can be characterized using the factors of batting, bowling, and decision-making. Further investigation suggests that the rank of the team and the number of runs they score have the most significant influence on the result of games. As far as the effectiveness of assigning bowlers is concerned, the Australian team has done a fabulous job compared to the rest of the teams.
W artykule przedstawiono problem przydziału pojazdów do zadań w przedsiębiorstwach usług komunalnych oraz model matematyczny problemu przydziału. Opisano metodę rozwiązującą omawiane zagadnienie oraz zaproponowano algorytm hybrydowy rozwiązujący zagadnienia optymalizacyjne przedstawionej metody. Algorytm hybrydowy jest kombinacją algorytmu genetycznego i mrówkowego. Algorytm mrówkowy generuje populację początkową dla algorytmu genetycznego. Wyniki algorytmu hybrydowego porównano z wynikami algorytmu mrówkowego, genetycznego z losową populacją początkową i algorytmu przeszukiwania losowego.
EN
This paper presents the assignment problem of vehicles to tasks in municipal services companies and the mathematical model of this problem. The article describes the method solving the discussed issue and proposes the hybrid algorithm solving the optimization problems of the presented method. The hybrid algorithm is a combination of the genetic and ant algorithm. The ant algorithm generates the initial population for the genetic algorithm. Results of the hybrid algorithm were compared with results of the ant algorithm, the genetic algorithm with the initial population selected randomly and random search algorithm.
Mutual destroying process on a battlefield has classically been modeled without accounting for the possible presence of false targets. Following [6] we include into consideration the presence of decoys. Attrition of human decoys is to be strenuously avoided for humanitarian reasons, but also because of its broad impact on world opinion. False targets should be taken into consideration in the formulation of the target assignment problems. We formulate bicriteria assignment problem. First of them maximizes expected value of destroyed correctly detected targets and the second minimizes expected value of destroyed incorrectly detected targets. The resulting problem provides the set of compromise solutions. Each of the considered assignment problems belong to the class of general assignment problem which does not contain totally unimodular matrix factors.
PL
W klasycznych modelach walki zwykle nie uwzględnia się obiektów źle zidentyfikowanych lub pozornych mających na celu zmylenie przeciwnika. W ślad za propozycją [6] taka obecność zostanie włączona do sformułowań zadań przydziału. Sformułowane zostanie dwukryterialne zadanie przydziału, w którym maksymalizuje się oczekiwaną wartość poprawnie zidentyfikowanych obiektów przeciwnika oraz minimalizuje oczekiwaną wartość niepoprawnie zidentyfikowanych obiektów. Takie sytuacje dotyczą działań bojowych w operacjach nietypowych, gdzie niszczenie obiektów, które nie są obiektami militarnymi, jest negatywnie oceniane z humanitarnego punktu widzenia. W problemie wynikowym proponuje się wyznaczenie rozwiązania kompromisowego przy pomocy znanych metod. Każdy ze sformułowanych problemów przydziału należy do klasy uogólnionych zadań przydziału i może nie posiadać unimodularnej macierzy współczynników.
The essence of the presented attrition process control relies on the solving defined sequence of target assignment problems at specific moments. The sequence of these moments is obtained for both sides of the battle. The model takes into account the changes of the number of means and targets as well as changes in environmental conditions. It is reflected in the parameters of problems. Each of the considered assignment problems belongs to the class of general assignment problems which does not contain totally unimodular matrix factors.
PL
Istotą proponowanego modelu sterowania procesem ubywania potencjałów w walce jest rozwiązywanie sekwencji zadań przydziału celów w określonych chwilach czasowych. Chwile te są wyznaczone dla obu stron walczących. Model uwzględnia zmiany liczby środków walki oraz zamiany warunków otoczenia. Odzwierciedlone jest to poprzez zmiany parametrów problemów. Każdy ze sformułowanych problemów należy do klasy uogólnionych zadań przydziału i może nie posiadać unimodularnej macierzy współczynników ograniczeń. Wskazano przykłady opracowanych metod rozwiązywania takich zadań.
The article defines the assignment problem of tasks to resources in a transport company. The paper describes mathematical model of a transport system taking into account the assignment of vehicles to the tasks. It also provides stages of creation of the genetic algorithm for solving the assignment problem in the transport company.
13
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The assignment problem consists of allocating renewable resources (construction equipment, crews, or contractors) of limited availability to a set of activities. The classical model for this problem minimizes the total time or cost of completing all activities with the assumption that each activity is assigned to one particular resource. This paper systematizes and describes extensions of these assumptions, considering the effects of task sequence: parallel, serial and hybrid (modeled by means of network methods). This study proposes algorithms for the solution of presented models, which can be used in construction project scheduling.
PL
W zagadnieniu przydziału (znanym również w literaturze pod nazwą zagadnienia rozmieszczenia) rozważa się problem alokacji ograniczonej liczby zasobów odnawialnych (maszyn, brygad, wykonawców) do realizacji zbioru zadań. W klasycznym modelu tego problemu jest minimalizowany łączny czas lub koszt wykonania wszystkich zadań przy założeniu, że każda jednostka organizacyjna jest przydzielona do realizacji innego procesu. W artykule przedstawiono usystematyzowanie i modyfikacje tych założeń z uwzględnieniem różnej kolejności realizacji procesów: równoczesnej, kolejnej i mieszanej (modelowanej za pomocą metod sieciowych). Zaproponowano algorytmy rozwiązania opracowanych modeli, które mogą być stosowane w harmonogramowaniu procesów budowlanych.
A bus station contains several bus stops. Only one bus can occupy a single bus stop at a time. Buses of many trips arrive to the bus station during the day (or during another considered period) and every bus occupies a bus stop for a certain time interval. The set of available bus stops is limited. This paper studies a problem how to assign a bus stop to every bus trip in order to minimize the number of assigned bus stops and in order to comply several additional conditions. Several approaches to this problem are presented. These approaches differ according to considered additional conditions.
PL
Na stacji autobusowej może znajdować się kilka platform. W tym samym czasie przy jednej platformie może znajdować się tylko jeden autobus. W ciągu dnia na stację autobusową przyjeżdżają autobusy z różnych połączeń i każdy z nich zajmuje platformę przez określony czas. Ten artykuł ma na celu pokazanie problemu przyporządkowania platform do wszystkich połączeń i jednoczesnej minimalizacji liczby platform przy spełnieniu określonych warunków. Prezentowane są różne sposoby rozwiązania problemu. Każdy ze sposobów różni się w zależności od dalszych warunków.
15
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
W artykule opisano problem przydziału zadań do zasobów w przedsiębiorstwie transportowym. Wyznaczono model matematyczny systemu transportowego uwzględniający przydział pojazdów do danych zadań transportowych. Przedstawiono etapy tworzenia algorytmu genetycznego rozwiązującego problem przydziału.
EN
The article defines an assignment problem of tasks to resources in the transport company. The paper describes the mathematical model of transport system taking into account the assignment of vehicle to tasks and shows stages of building of genetic algorithm solving an assignment problem in transport company.
W artykule zdefiniowano ogólny problem przydziału, wyjaśniono pojęcie skojarzenia w grafie dwudzielnym a następnie opisano problem przydziału w przedsiębiorstwie transportowym. Wyznaczono model matematyczny przydziału, funkcję optymalizacyjną.
EN
This article defines a general assignment problem and explains definition of a matching in a bipartite graph. This paper describes an assignment problem of tasks to resources in the transport company. This article contains the mathematical allocation model of tasks, function optimization with constrains.
Assignment Problem (AP), which is well known combinatorial problem, has been studied extensively in the course of many operational and technical researches. It has been shown to be NP-hard for three or more dimensions and a few non-deterministic methods have been proposed to solve it. This paper pays attention on new heuristic search method for the n-dimensional assignment problem, based on swarm intelligence and comparing results with those obtained by other scientists. It indicates possible direction of solutions of problems and presents a way of behaviour using ant algorithm for multidimensional optimization complex systems. Results of researches in the form of computational simulations outcomes are presented.
This paper presents an application of mixed integer programming model for optimal allocation of workers among supporting services in a hospital. The services include logistics, inventory management, financial management, operations management, medical analysis, etc. The optimality criterion of the problem is to minimize operational costs of supporting services subject to some specific constraints. The constraints represent specific conditions for resource allocation in a hospital. The overall problem is formulated as a triple-objective assignment model, where the decision variables represent the assignment of people to various jobs. A reference point approach with the Chebyshev metric is applied for the problem solution. The results of computational experiments modeled on a real data from a hospital in Lesser Poland are reported.
19
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
W pracy przedstawiono oryginalną metodę rozmieszczania elementów w układzie elektronicznym VLSI z wykorzystaniem sieci neuronowej typu Hopfielda. Celem rozmieszczenia elementów jest zapewnienie minimalnej sumarycznej długości połączeń w układzie. Określono postać funkcji energii, która jest minimalizowana przez sieć. W klasycznym rozwiązaniu wartości wag połączeń między neuronami w sieci są obliczane przed symulacją i nie ulegają zmianie. W niniejszej pracy zbadano wpływ zmian wartości wag podczas symulacji pracy sieci, na otrzymywane rozwiązania. Zauważono, że zmiana wartości wag umożliwia uzyskanie lepszych rozwiązań. Przedstawiono przykłady i wnioski płynące z zastosowania tej metody.
EN
The paper presents a novel method for solving two-dimensional assignment problems in electronic circuits. The method makes use of the Hopfield neural network. The aim of component placement is the minimization of the total length of interconnections in electronic circuits. The method makes use of the Hopfield net with continuous function of neurons according to Eq. (4). An energy function of the neural net is described by Eq. (9). This function consists of three components: the total length of interconnections between components in an electronic circuit and two terms, which make that all components are placed in separate cells of a substrate. Comparing Eq. (9) and Eq. (5), which is a general form of neural net energy function, we get Eqs. (10) and (11) for weight and external input signal values. We force the weight matrix to have zeros on the diagonal according to Eq. (14). The model Hopfield net in electronic components is shown in Figure 3. The Hopfield net is implemented in software in this work, a simulating program makes use of Eq. (21) to calculate the output of each neuron in the net. In conventional method weight values of the net are calculated before simulation and are constant. Our method is a novel method, because the weights are changed during simulation according to the algorithm shown in Figure 4. During the simulation the values of weights are changed in a linear way in accordance with Eq. (22). The speed of weight values changing is defined by a random value. Finally, a number of iterations to achieve a stable state of the net are done. A number of triaIs are performed for each assignment problem and the best results are chosen. Simulations were done for four examples of electronic circuits. The method with weight values changing during simulation gives better results than the conventional one. Results are performed in Table 3. Some conclusions coming from using this method are presented.
This paper presents a Cellular Neural Network (CNN) to solve the assignment problem of which the objective is to minimize the total cost of the assignment task. The Lyapunov function is considered as the function to be optimized via coefficients tuning to improve the solution and meet the constrains. The new method poses an additional exploitation of the CNN in this area of applications, which involve the concept of combinatorial optimization and intelligent decision in real time computation. The proposed algorithm has been evaluated through computer simulation for different sized to estimate the extension of the efficiency and capability to tackle this problem. This algorithm is applicable to industrial fields and can be integrated in some sort of intelligent unit for computation.
PL
W automatycznie wysegmentowany na obrazie dna W artykule przedstawiono wykorzystanie sieci neuronowej komórkowej (CNN) do rozwiązania problemu kombinatorycznego przydziału zadań I ich wykonawców przy minimalizacji całkowitego kosztu realizacji tych zadań. Problem minimalizacji z ograniczeniami przedstawiono w postaci funkcji Lapunowa sieci CNN o odpowiednio dobranych współczynnikach szablonu. Metoda pokazuje korzyści z zastosowania sieci CNN, do których należą jednoznaczność rozwiązania i bardzo krótki czas, pozwalający na wykonanie dużych zadań przydziału na bieżąco (w tzw. czasie rzeczywistym). Skuteczność algorytmu została zweryfikowana poprzez symulacje komputerowe wykonane dla problemów o różnych wymiarach. Nowy algorytm w postaci inteligentnego układu scalonego może być wykorzystany do optymalizacji procesów produkcji oraz zarządzania na bieżąco dużymi systemami.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.