An Air Force Crew Allocation and Scheduling Problem

This paper considers an airline crew allocation and scheduling problem faced by certain divisions of the United States Air Force. Two variants of the problem under consideration were posed to us by the U.S. Air Force. This paper reports our experience with two heuristic methods developed, each applicable to either variant of the problem. Although the problem described herein is peculiar to this situation, the heuristic scheduling and dispatching rules developed have been found to be very effective and are generally applicable in other related contexts of routeing and crew and vehicle scheduling problems as well. The two algorithms developed have been applied to a coded set of real world data. The results indicate that each one of the two methods is preferable to the other for one of the two variants of the problem. This suggests an overall effective composite technique.     

Hospital Layout as a Quadratic Assignment Problem

Journal of the Operational Research Society - The problem of locating hospital departments so as to minimize the total distance travelled by patients can be formulated as a Quadratic Assignment...     

Solving a Real World Assignment Problem with a Metaheuristic

This paper investigates a real world assignment problem, which slightly differs from the classical generalized assignment problem (GAP). The large-scale number of variables in the related 0-1 linear program makes the use of commercial optimization packages impractical. We present here a metaheuristic using simulated annealing. It is based on successive reductions of the search space by identification of locally active constraints. Our approach employs a heuristic procedure to compute an initial (feasible or infeasible) 0/1 solution, and a double-criterion acceptance rule. The performance of the algorithm is demonstrated on real data sets.     

Modeling and solving a logging camp location problem

Annals of Operations Research - Harvesting plans for Canadian logging companies tend to cover wider territories than before. Long transportation distances for the workers involved in logging...     

Crew Assignment via Constraint Programming: Integrating Column Generation and Heuristic Tree Search

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.     

An approach for solving a class of transportation scheduling problems

An algorithm is developed for solving a class of transportation scheduling problems. It applies for a variety of problems such as: the Combining Truck Trip problem, the Delivery problem, the School Bus problem, the Assignment of Buses to Schedules, and the Travelling Salesman problem. The objective functions of the above problems differ from each other. Yet, by using the “savings method” proposed by Clarke and Wright, and extended by Gaskell, we are able to define each one of the above problems as a series of assignment problems. The cost matrix entries of each one of the assignment problems are a function of the constraints of the particular routing or scheduling problem. The solution to the assignment problem determines an upper bound of the optimal solution to the original problem. By combining the above procedure with a Branch and Bound procedure, it is possible to obtain the optimal solution in a finite number of steps. In some cases the Branch and Bound process can be eliminated due to the nature of the problem and in those cases the algorithm is efficient.     

Modeling and solving physical problems

Generic operator equations allowing multidimensional operators are solved by a decomposition method allowing solution of nonlinear and/or stochastic partial differential equations by accurate and convenient approximation. Green's functions for complicated ordinary or partial differential linear equations are similarly determinable.     

Modeling and solving a real-life assignment problem at universities

A real-life problem of assigning students to exams during an examination period is modeled as an optimization problem over the set of maximal cliques of a specially structured weighted graph. The problem is solved using a combination of special-purpose heuristic and Tabu search. Numerical results of experiments with real-life data from Belgrade Law School are reported.     

Problem solving: a personal perspective from Brazil

In this paper, I do a historical review of the concept of Problem Solving, and make some considerations about the State of the Art nowadays. A very brief notice of the art of Problem Solving in Latin America is also presented. Finally, I present some reflections on the future of the Art of Problem Solving.     

指派问题的纳什均衡解

为弥补传统指派问题解不符合个体理性的不足,提出指派问题的纳什均衡解,并证明有限指派问题有且仅有纯纳什均衡解。相比传统的指派问题解,纯纳什均衡符合Pareto最优,是个体理性视角下的最优解。在此基础上,给出一个综合考虑个体理性与集体理性的求解方法。     

分配小于人数和任务数的指派问题的反点算法

摘要：本文对从 个人中派出 个人去完成 项任务中的 项任务使总效率最高这类指派问题给出了新算法,通过对这类指派问题引入了反点的概念,讨论了反点所具有的一些性质并证明了相关结论,利用这些结论找到了通过增加反点来解决此类指派问题的反点算法。     

一类广义指派问题的有效解法

提出一类广义指派问题,这类问题研究的是m个人执行n项任务,每个人执行的任务数、执行每项任务的人数以及总的指派人项数均有限制,要求最优指派.对这类广义指派问题建立了数学模型,并找到一种转换方法,将这类问题转换为平衡指派问题,从而用传统方法,如匈牙利法求解.最后用一个箅例来说明这种转换方法的简便和有效性.     

Using the Out-of-Kilter Algorithm to Solve a Complex Assignment Problem

The out-of-kilter algorithm is used to solve a complex assignment problem involving interacting and conflicting personal choices subject to interacting resource constraints. An example of successful use is given and extensions into the corporate and social planning fields are suggested.     

On the Multiple-machine Extension to a Common Due-date Assignment and Scheduling Problem

In a recent paper, Cheng considers the multiple-machine extension to a due-date assignment and scheduling problem. He implicitly assumes zero start times for all schedules (which does not ensure optimality), and overlooks the critical V-shape property for an optimal schedule (which leads him to over-estimate the effort needed to solve the problem). In this note, we correct these flaws, and also discuss the complexity of the problem and its special cases.     

Branch and bound procedures for solving the Assembly Line Worker Assignment and Balancing Problem: Application to Sheltered Work centres for Disabled

In this paper a new problem called Assembly Line Worker Assignment and Balancing Problem (ALWABP) is introduced. This problem arises in those assembly lines where we have certain limited resources available (normally workers) in which the operation time for every task is different depending on who executes the task, and where there are also some task-worker incompatibilities defined. The problem consists of providing a simultaneous solution to a double assignment: (1) tasks to stations; and (2) available workers to stations.After defining the mathematical model for this problem, a basic Branch and Bound approach with three possible search strategies and different parameters is presented. We also propose the use of a Branch and Bound-based heuristic for large problems and analyse the behaviour of both exact and heuristic methods through experimental studies. Finally the implementation of these procedures in a Sheltered Work centre for Disabled—the real environment which has inspired this research—is described. In these centres the adoption of assembly lines provide many advantages, since the traditional division of work in single tasks may become a perfect tool for making certain worker disabilities invisible. Efficiently applying this configuration helps these centres to achieve their primary aim: growth in order to provide more jobs for more disabled people, but always considering the specific limitations that the disabled workers have. In this sense this paper shows one of the possible real applications where Operations Research can help not only to get economic and productive benefits but also certain social aims.