Search

In fields like transport or materials sourcing, it is common industrial practice nowadays to contract several partners for the fulfilment of similar sets of tasks. A typical approach is to include quotes to the contracts that specify which portion of the total volume should be given to each partner. In this study, which is inspired by a real-world problem, we examine the question of operationally distributing jobs to a set of partners in order to meet the contracted quotes in different dimensions as closely as possible. We propose the term fair task allocation problem and analyze its complexity. While the problem is NP-hard in the strong sense for the general case, we show that it is solvable in pseudopolynomial time for a given number of partners and dimensions. Besides an exact solution approach based on dynamic programming, we present an efficient Tabu Search procedure. The Tabu Search is applied to real world as well as to self-generated instances. To verify its quality, the results are compared to the solutions of a commercial MIP-solver. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Personnel scheduling problems can be decomposed into two stages. In the first stage for each employee the working days have to be fixed. In the second stage for each day of the planning period an intraday scheduling problem has to be solved. It consists of the assignment of shifts to the employees who have to work on the day and for each working period of an employee a task assignment such that the demand of all tasks for personnel is covered. In Robinson et al. (Burke and Trick (Eds.), Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling, 18th August-20th August 2004, Pittsburgh, PA, USA, pp. 561-566, ), the intraday problem has been formulated as a maximum flow problem. The assumptions are that, employees are qualified for all tasks, their shifts are given, and they are allowed to change tasks during the day. In this work, we extend the network flow model to cover the case where not all employees are qualified to perform all tasks. The model is further extended to be able to calculate shifts of employees for the given day, assuming that an earliest starting time, a latest finishing time, and a minimal working time are given. Labour cost can be also taken into account by solving a minimum cost network flow problem. [ABSTRACT FROM AUTHOR]

This paper tackles a Nurse Scheduling Problem which consists of generating work schedules for a set of nurses while considering their shift preferences and other requirements. The objective is to maximize the satisfaction of nurses' preferences and minimize the violation of soft constraints. This paper presents a new deterministic heuristic algorithm, called MAPA (multi-assignment problem-based algorithm), which is based on successive resolutions of the assignment problem. The algorithm has two phases: a constructive phase and an improvement phase. The constructive phase builds a full schedule by solving successive assignment problems, one for each day in the planning period. The improvement phase uses a couple of procedures that re-solve assignment problems to produce a better schedule. Given the deterministic nature of this algorithm, the same schedule is obtained each time that the algorithm is applied to the same problem instance. The performance of MAPA is benchmarked against published results for almost 250,000 instances from the NSPLib dataset. In most cases, particularly on large instances of the problem, the results produced by MAPA are better when compared to best-known solutions from the literature. The experiments reported here also show that the MAPA algorithm finds more feasible solutions compared with other algorithms in the literature, which suggest that this proposed approach is effective and robust. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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: g 1-the maximum dissatisfaction of tasks, g 2-the total dissatisfaction of tasks, g 3-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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]