Search

Teamwork has increasingly become more popular in educational environments. With the also increasing mobility trends in the educational sector, internationalization and other diversity features have gained importance in the structure of teams. In this paper, we discuss an assignment problem arising in the allocation of students to business projects in a master program in Norway. Among other problem features, the students state their preferences on the projects they most want to conduct. There are also requirements from the companies that propose the projects and from the program administration. We develop a bi-objective approach to consider efficiency and fairness criteria in this assignment problem. We test the model using real data of 2017 and 2018, in joint collaboration with the administrative staff of the program. In light of the good results, our proposed solutions have been implemented in practice in 2019 and 2020. The implementation of these solutions have been beneficial for the administration, the students, and the companies.

We consider the patient-to-bed assignment problem that arises in hospitals. Both emergency patients who require hospital admission and elective patients who have had surgery need to be found a bed in the most appropriate ward. The patient-to-bed assignment problem arises when a bed request is made, but a bed in the most appropriate ward is unavailable. In this case, the next-best decision out of a many alternatives has to be made, according to some suitable decision making algorithm. We construct a Markov chain to model this problem in which we consider the effect on the length of stay of a patient whose treatment and recovery consists of several stages, and can be affected by stays in or transfers to less suitable wards. We formulate a dynamic program recursion to optimise an objective function and calculate the optimal decision variables, and discuss simulation techniques that are useful when the size of the problem is too large. We illustrate the theory with some numerical examples.

The top two divisions of the Argentinean professional basketball system have since 2014–2015 used a season schedule format similar to that used by the NBA in which games are played all through the week, replacing the previous setup where all games were scheduled on weekends. This change has confronted the Argentinean league organizers with new scheduling challenges, one of which is the assignment of referees to games. The present article addresses this assignment problem using a tool based on an integer linear programming model. The objective is to minimize the total cost of trips made by the referees while also satisfying a series of other conditions. The problem is broken down into a series of relatively small subproblems representing successive periods of the season, and the solution is obtained using a rolling horizon heuristic. The approach was tested by applying it to the First Division’s 2015–2016 season, the last one before introducing the approach presented in this article, when referees were still assigned using manual methods. The travel costs simulated by the model were 26% lower than the total travel costs actually incurred under the manual assignments, and all of the restrictions that had been requested by league officials were satisfied. The model was used by the First Division for the 2016–2017 and 2017–2018 seasons and in 2017–2018 also by the Second Division.

In this paper, we develop a new bi-objective model for dynamic weapon-target assignment problem. We consider that the initial weapon assignment plan of defense is disrupted during engagement because of a destroyed air target, breakdown of a weapon system or a new incoming air target. The objective functions are defined as the maximization of probability of no-leaker and the maximization of stability in engagement order of weapon systems. Stability is defined as assigning same air target in sequence in engagement order of a weapon system so that reacquisition and re-tracking of air target are not required by sensors. We propose a new solution procedure to generate updated assignment plans by maximizing efficiency of defense while maximizing stability through swapping weapon engagement orders. The proposed solution procedure generates non-dominated solutions from which defense can quickly choose the most-favored course of action. We solve a set of representative problems with different sizes and present computational results to evaluate effectiveness of the proposed approach.

Over the past couple of centuries, with the increase in the significance of the railways to the economy, the complexity of the railway network and consequently the decision making involved and the number of problems faced has only increased. Among the host of problems in railways management, one of the most important is the locomotive assignment problem (LAP). The LAP is as old as the railways itself. The objective of the LAP is to assign a fleet of locomotives at minimum cost to pre-scheduled trains subject to a host of constraints. Most of the models in literature either work on improving the efficiency of solving the LAP or attempt to solve the three levels of LAP separately. Our attempt in this paper is to arrive at a linear mathematical model that integrates the strategic, tactical and operational level aspects of the LAP. We also demonstrate that by the addition of a valid inequality, the lower bounds can be improved substantially resulting in a substantial reduction in solution times for the problem instances. Further, we develop a Dijkstra’s algorithm-based heuristic to test the problem instances and compare the solution times and quality of solutions. Finally, we develop a case based on Southern Zone of the Indian Railways and test the heuristic to solve the LAP for this zone.

Suppose we like to find non-overlapping periods for a set of events which may have multiple teachers assigned, is this easy or hard in terms of complexity? Or assume that only a single teacher is fixed per event, but we like to allocate rooms and periods simultaneously. What if a single teacher and a room is already given and we look for periods alone? And how do requests of teachers for specific rooms or additional student conflicts change the computational complexities of these questions from university course timetabling (UCT)? We provide a complete hard/easy-list of all UCT subproblems derived from a typical set of hard constraints. We obtain this list with a systematic study of the fine structure of UCT in terms of complexity w.r.t. the order in which rooms, periods and teachers are assigned to events. These kind of subproblems appear in practice when some entities in a timetable are fixed while the assignments of others are (re-)computed, and they also appear as necessary conditions for the existence of feasible timetables. Moreover, we identify which of the seemingly different subproblems are essentially the same computational tasks by reducing them to the same bipartite assignment problem, and we discuss some variations of constraints.

This paper considers the integration of three essential seaport terminal operations: the berth allocation problem, the quay crane assignment problem (QCAP), and the quay crane scheduling problem (QCSP). The paper presents a new mathematical formulation that captures all associated operations and constraints. Different quay crane operational policies are considered, namely permitting versus not permitting bay task preemption in QCSP and static versus dynamic crane allocations in QCAP. Thus, variants of the mathematical formulation are introduced to capture the different combinations of these scenarios. Due to the preemption consideration, the models include disaggregated quay crane (QC) tasks. Specifically, QC tasks are identified by single container movements as opposed to bay or stack task allocations that are commonly used in the literature. A case study based on Abu Dhabi’s container terminal is presented where the use of the proposed mathematical models are compared against the current existing operational approach. Results show that the service times can be significantly decreased by the use of the proposed models. Moreover, the policy choice effect on the total schedule is compared through simulated examples and Abu Dhabi’s container terminal case study. The results show that the policy improvements can depend on the problem’s attributes and thus a better policy cannot be generalized.

The Reformulation Linearization Technique (RLT) of Sherali and Adams (Manag Sci 32(10):1274–1290, 1986; SIAM J Discrete Math 3(3):411–430, 1990), when applied to a pure 0–1 quadratic optimization problem with linear constraints (P), constructs a hierarchy of LP (i.e., continuous and linear) models of increasing sizes. These provide monotonically improving continuous bounds on the optimal value of (P) as the level, i.e., the stage in the process, increases. When the level reaches the dimension of the original solution space, the last model provides an LP bound equal to the IP optimum. In practice, unfortunately, the problem size increases so rapidly that for large instances, even computing bounds for RLT models of level k (called RLTk) for small k may be challenging. Their size and their complexity increase drastically with k. To our knowledge, only results for bounds of levels 1, 2, and 3 have been reported in the literature. We are proposing, for certain quadratic problem types, a way of producing stronger bounds than continuous RLT1 bounds in a fraction of the time it would take to compute continuous RLT2 bounds. The approach consists in applying a specific decomposable Lagrangean relaxation to a specially constructed RLT1-type linear 0–1 model. If the overall Lagrangean problem does not have the integrality property, and if it can be solved as a 0–1 rather than a continuous problem, one may be able to obtain 0–1 RLT1 bounds of roughly the same quality as standard continuous RLT2 bounds, but in a fraction of the time and with much smaller storage requirements. If one actually decomposes the Lagrangean relaxation model, this two-step procedure, reformulation plus decomposed Lagrangean relaxation, will produce linear 0–1 Lagrangean subproblems with a dimension no larger than that of the original model. We first present numerical results for the Crossdock Door Assignment Problem, a special case of the Generalized Quadratic Assignment Problem. These show that just solving one Lagrangean relaxation problem in 0–1 variables produces a bound close to or better than the standard continuous RLT2 bound (when available) but much faster, especially for larger instances, even if one does not actually decompose the Lagrangean problem. We then present numerical results for the 0–1 quadratic knapsack problem, for which no RLT2 bounds are available to our knowledge, but we show that solving an initial Lagrangean relaxation of a specific 0–1 RLT1 decomposable model drastically improves the quality of the bounds. In both cases, solving the fully decomposed rather than the decomposable Lagrangean problem to optimality will make it feasible to compute such bounds for instances much too large for computing the standard continuous RLT2 bounds.

The berth allocation and quay crane assignment problem (BACAP) is a complex port operation planning problem susceptible to uncertainties, such as vessel arrival time fluctuation to its estimated time of arrival and maritime markets. For promoting reliability and sustainability of container terminals, this paper addresses the optimization of BACAP under the uncertain vessels’ arrival times and fluctuation of loading and unloading volumes. We propose a proactive BACAP strategy considering minimum recovery cost under uncertainty using a reactive strategy. A stochastic programming model is formulated to minimize the basic cost in the baseline schedule, and the recovery cost in real uncertain scenarios. A two-stage meta-heuristic framework based on GA is developed for solving this problem. Numerical experiments and scenario analysis are conducted to validate the effectiveness of the proposed model and the proposed solution approaches.

In this article, we investigate the vehicle assignment problem with demand uncertainty in a hybrid hub-and-spoke network with a single hub. The problem is deciding both the transportation routes and the number and types of vehicles to be deployed to minimize the sum of costs to transport all quantities in a hybrid hub-and-spoke network which allows direct transportation between spokes. Daily changes in quantities are reflected with a finite number of scenarios. Regularly scheduled vehicles and temporarily scheduled vehicles are considered to meet the demand variation. We propose a Dantzig–Wolfe decomposition approach which yields a strong LP relaxation bound by introducing a set of feasible direct route patterns. We develop an algorithm which incorporates a column generation procedure at the root node and repeats iteratively a variable fixing and column generation procedure at the non-root nodes until an integral solution is found. Finally, we present computational results using the well-known CAB data sets and real-life data from the Korea Post. The results show that our algorithm can find near optimal solutions very efficiently.

Falls represent a considerable public health problem, especially in older population. We describe and evaluate data-driven operations research models for detection and situational assessment of falls and near falls with a system of wearable sensors. The models are formulated as instances of the multidimensional assignment problem. Our computational studies provide some initial empirical evidence of the potential usefulness of this new application of the multidimensional assignment problem.

A two-phase approach was adopted to solve the problem given during the ROADEF/EURO Challenge 2014 competition. The problem focuses on rolling stock management at railway sites, as defined by French Railways (SNCF). In the first phase, a train assignment problem is solved by combining a greedy heuristic procedure with integer programming. The objective is to maximize the number of assigned departures while meeting technical constraints. The second phase consists of scheduling train movements inside the station while minimizing the number of cancelled (uncovered) arrivals and departures. This schedule has to comply with resource constraints such as capacity, length, order of trains, etc. A constructive heuristic is used to build a feasible schedule, which is subject to improvement by an iterative procedure based on a local search. Experiment results, that demonstrate the effectiveness of our approach on the large scale instances provided by SNCF, are presented hereafter.

We consider a bilevel extension of the classical linear assignment problem motivated by network interdiction applications. Specifically, given a bipartite graph with two different (namely, the leader’s and the follower’s) edge costs, the follower solves a linear assignment problem maximizing his/her own profit, whereas the leader is allowed to affect the follower’s decisions by eliminating some of the vertices from the graph. The leader’s objective is to minimize the total cost given by the cost of the interdiction actions plus the cost of the assignments made by the follower. The considered problem is strongly $${ NP}$$ -hard. First, we formulate this problem as a linear mixed integer program (MIP), which can be solved by commercial MIP solvers. More importantly, we also describe a greedy-based construction heuristic, which provides (under some mild conditions) an optimal solution for the case, where the leader’s and the follower’s edge costs are equal to one. Finally, we present the results of our computational experiments comparing the proposed heuristic against an MIP solver.

Semidefinite optimization is a strong tool in the study of NP-hard combinatorial optimization problems. On the one hand, semidefinite optimization problems are in principle solvable in polynomial time (with fixed precision), on the other hand, their modeling power allows to naturally handle quadratic constraints. Contrary to linear optimization with the efficiency of the Simplex method, the algorithmic treatment of semidefinite problems is much more subtle and also practically quite expensive. This survey-type article is meant as an introduction for a non-expert to this exciting area. The basic concepts are explained on a mostly intuitive level, and pointers to advanced topics are given. We provide a variety of semidefinite optimization models on a selection of graph optimization problems and give a flavour of their practical impact.

Population growth and the massive production of automotive vehicles have lead to the increase of traffic congestion problems. Traffic congestion today is not limited to large metropolitan areas, but is observed even in medium-sized cities and highways. Traffic engineering can contribute to lessen these problems. One possibility, explored in this paper, is to assign tolls to streets and roads, with the objective of inducing drivers to take alternative routes, and thus better distribute traffic across the road network. This assignment problem is often referred to as the tollbooth problem and it is NP-hard. In this paper, we propose mathematical formulations for two versions of the tollbooth problem that use piecewise-linear functions to approximate congestion cost. We also apply a biased random-key genetic algorithm on a set of real-world instances, analyzing solutions when computing shortest paths according to two different weight functions. Experimental results show that the proposed piecewise-linear functions approximate the original convex function quite well and that the biased random-key genetic algorithm produces high-quality solutions.

Evacuations are massive operations that create heavy travel demand on road networks some of which are experiencing major congestions even with regular traffic demand. Congestion in traffic networks during evacuations, can be eased either by supply or demand management actions. This study focuses on modeling demand management strategies of optimal departure time, optimal destination choice and optimal zone evacuation scheduling (also known as staggered evacuation) under a given fixed evacuation time assumption. The analytical models are developed for a system optimal dynamic traffic assignment problem, so that their characteristics can be studied to produce insights to be used for large-scale solution algorithms. While the first two strategies were represented in a linear programming (LP) model, evacuation zone scheduling problem inevitable included integers and resulted in a mixed integer LP (MILP) one. The dual of the LP produced an optimal assignment principle, and the nature of the MILP formulations revealed clues about more efficient heuristics. The discussed properties of the models are also supported via numerical results from a hypothetical network example.

This paper considers the component assignment problem (CAP) of finding the optimal assignment of n available components to n positions in a system such that the system reliability is maximized. To solve the CAP, an important type of problems in reliability, we propose a Birnbaum-importance based genetic local search (BIGLS) algorithm in which a local search using the Birnbaum importance is embedded into the genetic algorithm. This paper presents comprehensive numerical tests to compare the performance of the BIGLS with a general genetic algorithm and a Birnbaum-importance based two-stage heuristic. The testing results show that the BIGLS is robust (with respect to its random operations) and effective, and outperforms two benchmark methods in terms of solution quality. It demonstrates the effectiveness of embedding the Birnbaum importance in the local search under the genetic evolutionary mechanism.

In this paper, a multiobjective scatter search procedure for a bi-objective territory design problem is proposed. A territory design problem consists of partitioning a set of basic units into larger groups that are suitable with respect to some specific planning criteria. These groups must be compact, connected, and balanced with respect to the number of customers and sales volume. The bi-objective commercial territory design problem belongs to the class of NP-hard problems. Previous work showed that large instances of the problem addressed in this work are practically intractable even for the single-objective version. Therefore, the use of heuristic methods is the best alternative for obtaining approximate efficient solutions for relatively large instances. The proposed scatter search-based framework contains a diversification generation module based on a greedy randomized adaptive search procedure, an improvement module based on a relinked local search strategy, and a combination module based on a solution to an assignment problem.

We consider the bilevel road pricing problem. In contrary to the Karush-Kuhn-Tucker (one level) reformulation, the optimal value reformulation is globally and locally equivalent to the initial problem. Moreover, in the process of deriving optimality conditions, the optimal value reformulation helps to preserve some essential data involved in the traffic assignment problem that may disappear with the Karush-Kuhn-Tucker (KKT) one. Hence, we consider in this work the optimal value reformulation of the bilevel road pricing problem; using some recent developments in nonsmooth analysis, we derive implementable KKT type optimality conditions for the problem containing all the necessary information. The issue of estimating the (fixed) demand required for the road pricing problem is a quite difficult problem which has been also addressed in recent years using bilevel programming. We also show how the ideas used in designing KKT type optimality conditions for the road pricing problem can be applied to derive optimality conditions for the origin-destination (O-D) matrix estimation problem. Many other theoretical aspects of the bilevel road pricing and O-D matrix estimation problems are also studied in this paper.

The weakest link principle applies to many real-life situations where a system is as productive as its bottleneck. The purpose of this paper is to show how the efficiency of a manufacturing or service process (i.e., the strength of a chain) may be maximized by optimal allocation of resources to improve the performance of the bottleneck (i.e., strengthen the weakest link) in an uncertain environment. Specifically, we consider two different versions of the stochastic bottleneck assignment problem (SBAP), which is a variation of the classic assignment problem (AP), with respective goals of minimizing the expected longest processing time and maximizing the expected lowest production rate. It is proven that each of the two intrinsically difficult SBAPs is reducible to an efficiently solvable AP provided that the processing times or the production rates are independent random variables following some families of probability distributions.

I consider the problem of weekly assignment of shifts to operators. The shifts are to be assigned by seniority (or by any other employee hierarchy), but every employee is guaranteed to receive at least one shift. I propose a practical solution method to this problem that guarantees a feasible solution. As an application, the solution method is applied to the data provided in the literature on weekly shift assignment of the operators of the New Brunswick Telephone company. The solution method is also applied to 100 randomly generated problems. The results show that the solution method produces close-to-optimal solutions.

Recently, crossdocking techniques have been successfully applied in responsive supply chain management. However, most researches focused on physical layout of a crossdock, or scheduling operations within a crossdock. In this paper, we study a multi-crossdock transshipment service problem with both soft and hard time windows. The flows from suppliers to customers via the crossdocks are constrained by fixed transportation schedules. Cargos can be delayed and consolidated in crossdocks, and both suppliers and customers have specific hard time windows. In addition to hard time windows, customers also have less-restrictive time windows, called soft time windows. The problem to minimize the total cost of the multi-crossdock distribution network, including transportation cost, inventory handling cost and penalty cost, can be proved to be NP-hard in the strong sense and hence efficient heuristics are desired. We propose two types of meta-heuristic algorithms, called Adaptive Tabu Search and Adaptive Genetic Algorithm, respectively, to solve the problem efficiently. We conduct extensive experiments and the results show that both of them outperform CPLEX solver and provide fairly good solutions within realistic timescales. We also perform sensitivity analysis and obtain a number of managerial insights.

The rectangular assignment problem is a generalization of the linear assignment problem (LAP): one wants to assign a number of persons to a smaller number of jobs, minimizing the total corresponding costs. Applications are, e.g., in the fields of object recognition and scheduling. Further, we show how it can be used to solve variants of the LAP, such as the k-cardinality LAP and the LAP with outsourcing by transformation. We introduce a transformation to solve the machine replacement LAP.We describe improvements of a LAP-algorithm for the rectangular problem, in general and slightly adapted for these variants, based on the structure of the corresponding cost matrices. For these problem instances, we compared the best special codes from literature to our codes, which are more general and easier to implement. The improvements lead to more efficient and robust codes, making them competitive on all problem instances and often showing much shorter computing times.

We consider some variant models, having changeover cost, of the assignment problem. In these models, multiple assignments to an operator are allowed. In addition to assignment costs, a changeover cost is incurred if an operator does one job after another is completed. Two different types of changeover costs and related two models are considered. Mathematical programming formulations are given for the models. When changeover costs are dependent on the operator but independent of the jobs and are non-negative, a linear programming model is obtained. For the case when changeover costs are dependent on the jobs, a linear integer programming formulation is obtained. We also show that, this problem is strongly NP-hard. A heuristic solution method is suggested for it. Numerical findings on the performance of the method are given.

Two metaheuristic methods based on Tabu search are introduced to assign judges to individual competitions in a tournament. The complexity of the mathematical formulation accounting for the assignment rules, leads us to use such an approach. The first metaheuristic includes two different Tabu searches that are combined with a diversification strategy. The second metaheuristic is applied to a penalized version of the original model formulated as an assignment problem. This metaheuristic is also based on a Tabu search procedure including a diversification strategy driven by the constraints violated. Numerical results are provided to indicate the efficiency of the methods to generate very good solutions.

The Multi-Story Space Assignment Problem (MSAP) is an innovative formulation of the multi-story facility assignment problem that allows one to model the location of departments of unequal size within multi-story facilities as a Generalized Quadratic 3-dimensional Assignment Problem (GQ3AP). Not only can the MSAP generate the design of the location of the departments in the facility, the MSAP also includes the evacuation planning for the facility. The formulation, background mathematical development, and computational experience with a branch and bound algorithm for the MSAP are also presented.

Within the area of short term airline operational planning, Tail Assignment is the problem of assigning flight legs to individual identified aircraft while satisfying all operational constraints, and optimizing some objective function. In this article, we propose that Tail Assignment should be solved as part of both the short and the long term airline planning. We further present a hybrid column generation and constraint programming solution approach. This approach can be used to quickly produce solutions for operations management, and also to produce close-to-optimal solutions for long and mid term planning scenarios. We present computational results which illustrate the practical usefulness of the approach.

The considered assignment problem generalizes its classical counterpart by the existence of some incompatibility constraints limiting the assignment of tasks to processing units within groups of mutually exclusive tasks. The groups are defined for each processing unit and the constraints allow at most one task from each group to be assigned to the corresponding processing unit. The processing units can normally process a certain number of tasks without any cost; this capacity can be extended, however, at some extra marginal cost that is non-decreasing with the number of additional tasks. Each task has to be assigned to exactly one processing unit and has some preference for the assignment; it is expressed for each pair ‘task-processing unit’ by a dissatisfaction degree. The quality of feasible assignments is evaluated by three criteria: g1-the maximum dissatisfaction of tasks, g2-the total dissatisfaction of tasks, g3-the total cost of processing units. If there is no feasible assignment, tasks and processing units creating a blocking configuration are identified and all actions of unblocking are proposed. Formal properties of blocking configurations and unblocking actions are proven, and an interactive procedure for exploring the set of non-dominated assignments is described together with illustrative examples processed by special software.

The data association problem consists of associating pieces of information emanating from different sources in order to obtain a better description of the situation under study. This problem arises, in particular, when, considering several sensors, we aim at associating the measures corresponding to a same target. This problem, widely studied in the literature, is often stated as a multidimensional assignment problem where a state criterion is optimized. While this approach seems satisfactory in simple situations where the risk of confusing targets is relatively low, it is much more difficult to get a correct description in denser situations. This is why, we propose, for the first time to our knowledge, to address this problem in a multiple criteria framework using a second complementary criterion, based on the identification of the targets. Due to the specificities of the problem, simple and efficient approaches can be used to generate non-dominated solutions. Moreover, we show that the accuracy of the proposed solutions is greatly increased when considering a second criterion. A bi-criteria interactive procedure is also introduced to assist an operator in solving conflicting situations.

We apply Algorithm Robust to various problems in multiple objective discrete optimization. Algorithm Robust is a general procedure that is designed to solve bicriteria optimization problems. The algorithm performs a weight space search in which the weights are utilized in min-max type subproblems. In this paper, we experiment with Algorithm Robust on the bicriteria knapsack problem, the bicriteria assignment problem, and the bicriteria minimum cost network flow problem. We look at a heuristic variation that is based on controlling the weight space search and has an indirect control on the sample of efficient solutions generated. We then study another heuristic variation which generates samples of the efficient set with quality guarantees. We report results of computational experiments.

In the assignment problem units of supply are assigned on a one-to-one basis to units of demand so as to minimize the sum of the cost associated with each supply-to-demand matched pair. Defined on a network, the supplies and demands are located at vertices and the cost of a supply-to-demand matched pair is the distance between them. This paper considers a two-stage stochastic program for locating the units of supply based upon only a probabilistic characterization of demand. The objective of the first-stage location problem is to minimize the expected cost of the second-stage assignment problem. Principal results include showing that the problem is NP-hard on a general network, has a simple solution procedure on a line network, and is solvable by a low order polynomial greedy procedure on a tree network. Potential applications are discussed.

In previous work the authors consider the dynamic assignment problem, which involves solving sequences of assignment problems over time in the presence of uncertain information about the future. The algorithm proposed by the authors provides generally high-quality but non-optimal solutions. In this work, though, the authors prove that if the optimal solution to a dynamic assignment problem in one of two problem classes is unique, then the optimal solution is a fixed point under the algorithm.

The Airline Crew Assignment Problem (ACA) consists of assigning lines of work to a set of crew members such that a set of activities is partitioned and the costs for that assignment are minimized. Especially for European airline companies, complex constraints defining the feasibility of a line of work have to be respected. We developed two different algorithms to tackle the large scale optimization problem of Airline Crew Assignment. The first is an application of the Constraint Programming (CP) based Column Generation Framework. The second approach performs a CP based heuristic tree search. We present how both algorithms can be coupled to overcome their inherent weaknesses by integrating methods from Constraint Programming and Operations Research. Numerical results show the superiority of the hybrid algorithm in comparison to CP based tree search and column generation alone.

Most writers on frequency assignment algorithms have described the details of a single algorithm, and evaluated the algorithm on selected data sets. There has been relatively little emphasis on describing the common features that are important if an algorithm is to have good performance. This paper describes the key features, with particular emphasis on algorithms for weighted fixed spectrum problems. The use of algorithms handling weighted constraints has become increasingly common in recent years. The advantages and disadvantages of weighting constraints are demonstrated.

This paper presents a surrogate constraint tabu thresholding (SCTT) implementationfor solving the frequency assignment problem. The frequency assignment problem is animportant combinatorial optimisation problem that arises in telecommunications. The mainobjective is to assign radio frequencies to a number of communication links such that interferenceis minimised. Interference is minimised by satisfying a number of problem specificconstraints. The surrogate constraint is created by taking a weighted sum of the constraintsnot satisfied. SCTT is compared with a tabu thresholding method from the literature on a setof simulated but realistic test problems with respect to quality of the solution in a given timeperiod. Computational results show that SCTT is more efficient and effective for all the testproblems.

The Best‐First Search strategy (BeFS) and the Depth‐First Search strategy (DFS) areregarded as the prime strategies when solving combinatorial optimization problems by parallelBranch‐and‐Bound (B&B) ‐ BeFS because of efficiency with respect to the number of nodesexplored, and DFS for reasons of space efficiency.

To date, there has been a lack of efficient and practical distributed‐ and shared‐memoryparallelizations of the data association problem for multitarget tracking. Filling this gap is oneof the primary focuses of the present work. We begin by describing our data association algorithmin terms of an Interacting Multiple Model (IMM) state estimator embedded into anoptimization framework, namely, a two‐dimensional (2D) assignment problem (i.e., weightedbipartite matching). Contrary to conventional wisdom, we show that the data association (oroptimization) problem is not the major computational bottleneck; instead, the interface to theoptimization problem, namely, computing the rather numerous gating tests and IMM stateestimates, covariance calculations, and likelihood function evaluations (used as cost coefficientsin the 2D assignment problem), is the primary source of the workload. Hence, for both ageneral-purpose shared‐memory MIMD (Multiple Instruction Multiple Data) multiprocessorsystem and a distributed‐memory Intel Paragon high‐performance computer, we developedparallelizations of the data association problem that focus on the interface problem. For theformer, a coarse‐grained dynamic parallelization was developed that realizes excellent performance(i.e., superlinear speedups) independent of numerous factors influencing problemsize (e.g., many models in the IMM, denseycluttered environments, contentious target‐measurementdata, etc.). For the latter, an SPMD (Single Program Multiple Data) parallelization wasdeveloped that realizes near‐linear speedups using relatively simple dynamic task allocationalgorithms. Using a real measurement database based on two FAA air traffic control radars, weshow that the parallelizations developed in this work offer great promise in practice.

The purpose of this study is to develop an efficient heuristic for the process selection and part cell assignment problem. The study assumes a production environment where each part has several process plans, each manifested by a required set of tools. These tools can be assigned to different machines based on a tool-machine compatibility matrix. An additional assumption is that all relevant data such as periodic demand, processing time, processing cost, tool magazine capacity, tool changing time, tool life and tool cost are fixed and known. A mixed integer linear program which takes all relevant data into account is developed to minimize the production cost. The suggested solution approach to solve this model makes use of Genetic Algorithms: a class of heuristic search and optimization techniques that imitate the natural selection and evolutionary process. First, the encoding of the solutions into integer strings is presented, as well as the genetic operators used by the algorithm. Next, the efficiency and robustness of the solution procedure is demonstrated through several different examples.

The combined distribution and assignment problem is the problem of the simultaneousdetermination of the distribution of trips between origins and destinations in a transportationnetwork and the assignment of trips to routes in each origin - destination pair. In the modelmost widely used, the distribution is assumed to follow a gravity model with a negativeexponential deterrence function and the assignment is made according to the deterministicuser equilibrium principle. In this paper, we describe an extension of this model in whichthe allocation of trips to routes is made according to the principle of stochastic user equilibrium.We discuss the behavioural foundations of trip assignment and combined modelsassuming deterministic or stochastic route choice. In particular, we describe how they can bederived using the efficiency principle from discrete choice theory; the combined distributionand stochastic assignment model is obtained as the continuous approximation of the discreteproblem of finding the most probable flow pattern under the assumption of efficient tripmaking behaviour. We outline an algorithm for the solution of the model which is based onroute (column) generation, disaggregate simplicial decomposition, and partial linearization.