A simple dual algorithm for the generalised assignment problem

A new algorithm for the generalised assignment problem is described in this paper. The dual-type algorithm uses a simple heuristic derived from a relaxation of the problem. The algorithm has been tested on generalised assignment problems of substantial size and compared to an exact integer programming approach and a well-established heuristic approach. Computational results look promising in terms of speed and solution quality.     

Evaluation of the multiobjective ant colony algorithm performances on biobjective quadratic assignment problems

The difficulty of resolving the multiobjective combinatorial optimization problems with traditional methods has directed researchers to investigate new approaches which perform better. In recent years some algorithms based on ant colony optimization (ACO) metaheuristic have been suggested to solve these multiobjective problems. In this study these algorithms have been reported and programmed both to solve the biobjective quadratic assignment problem (BiQAP) instances and to evaluate the performances of these algorithms. The robust parameter sets for each 12 multiobjective ant colony optimization (MOACO) algorithms have been calculated and BiQAP instances in the literature have been solved within these parameter sets. The performances of the algorithms have been evaluated by comparing the Pareto fronts obtained from these algorithms. In the evaluation step, a multi significance test is used in a non hierarchical structure, and a performance metric (P metric) essential for this test is introduced. Through this study, decision makers will be able to put in the biobjective algorithms in an order according to the priority values calculated from the algorithms’ Pareto fronts. Moreover, this is the first time that MOACO algorithms have been compared by solving BiQAPs.     

Heuristic Solution Methods for the Multilevel Generalized Assignment Problem

The multilevel generalized assignment problem is a problem of assigning agents to tasks where the agents can perform tasks at more than one efficiency level. A profit is associated with each assignment and the objective of the problem is profit maximization. Two heuristic solution methods are presented for the problem. The heuristics are developed from solution methods for the generalized assignment problem. One method uses a regret minimization approach whilst the other method uses a repair approach on a relaxation of the problem. The heuristics are able to solve moderately large instances of the problem rapidly and effectively. Procedures for deriving an upper bound on the solution of the problem are also described. On larger and harder instances of the problem one heuristic is particularly effective.     

Simple Heuristics for the School Assignment Problem

Several simple heuristic procedures are described for solving the pupils-school assignment problem. These methods have been applied to a real-life problem in Switzerland.     

A Lagrangian relaxation-based heuristic for the vehicle routing with full container load

We address a problem of vehicle routing that arises in picking up and delivering full container load from/to an intermodal terminal. The substantial cost and time savings are expected by efficient linkage between pickup and delivery tasks, if the time of tasks and the suitability of containers for cargo allow. As this problem is NP-hard, we develop a subgradient heuristic based on a Lagrangian relaxation which enables us to identify a near optimal solution. The heuristic consists of two sub-problems: the classical assignment problem and the generalized assignment problem. As generalized assignment problem is also NP-hard, we employ an efficient solution procedure for a bin packing based problem, which replaces the generalized assignment problem. The heuristic procedure is tested on a wide variety of problem examples. The test results demonstrate that the procedure developed here can efficiently solve large instances of the problem.     

An Improved Heuristic for the Quadratic Assignment Problem

A technique is described whereby the computational efficiency of the Lashkari-Jaisingh heuristic for the quadratic assignment problem is greatly enhanced. Results for the modified heuristic are presented which demonstrate that it provides solutions of consistently high quality at relatively small computational cost.     

Effective algorithm and heuristic for the generalized assignment problem

We present new Branch-and-Bound algorithm for the generalized assignment problem. A standard subgradient method (SM), used at each node of the decision tree to solve the Lagrangian dual, provides an upper bound. Our key contribution in this paper is a new heuristic, applied at each iteration of the SM, which tries to exploit the solution of the relaxed problem, by solving a smaller generalized assignment problem. The feasible solution found is then subjected to a solution improvement heuristic. We consider processing the root node as a Lagrangian heuristic. Computational comparisons are made with new existing methods.     

A morph-based simulated annealing heuristic for a modified bin-packing problem

This paper presents a local-search heuristic, based on the simulated annealing (SA) algorithm for a modified bin-packing problem (MBPP). The objective of the MBPP is to assign items of various sizes to a fixed number of bins, such that the sum-of-squared deviation (across all bins) from the target bin workload is minimized. This problem has a number of practical applications which include the assignment of computer jobs to processors, the assignment of projects to work teams, and infinite-loading machine scheduling problems. The SA-based heuristic we developed uses a morph-based search procedure when looking for better allocations. In a large computational study we evaluated 12 versions of this new heuristic, as well as two versions of a previously published SA-based heuristic that used a completely random search. The primary performance measure for this evaluation was the mean percent above the best known objective value (MPABKOV). Since the MPABKOV associated with the best version of the random-search SA heuristic was more than 290 times larger than that of the best version of the morph-based SA heuristic, we conclude that the morphing process is a significant enhancement to SA algorithms for these problems.     

Transit passenger origin-destination estimation in congested transit networks with elastic line frequencies

This paper deals with the transit passenger origin-destination (O-D) estimation problem by using updated passenger counts in congested transit networks and outdated prior O-D matrix. A bilevel programming approach is extended for the transit passenger O-D updating problem where the upper-level problem seeks to minimize the sum of error measurements in passenger counts and O-D matrices, while the lower level is the stochastic user equilibrium assignment problem for congested transit networks. The transit assignment framework is based on a frequency-adaptive transit network model in this paper, which can help determine transit line frequencies and the network flow pattern simultaneously in congested transit networks. A heuristic solution algorithm is adapted for solving the transit passenger O-D estimation problem. Finally, a numerical example is used to illustrate the applications of the proposed model and solution algorithm. The work described in this paper was mainly supported by two research grants from the Research Grants Council of the Hong Kong Special Administrative Region (Project No. PolyU 5143/03E and PolyU 5040/02E).     

Routing and wavelength assignment by partition colouring

The problem of routing and wavelength assignment in all-optical networks may be solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a partition colouring problem in a conflict graph. A new tabu search heuristic is also proposed for the partition colouring problem, which may be viewed as an extension of the graph colouring problem. Computational experiments are reported, showing that the tabu search heuristic outperforms the best heuristic for partition colouring by approximately 20% in the average and illustrating that the new approach for the problem of routing and wavelength assignment is more robust than a well established heuristic for this problem.     

A mathematical model and two-stage heuristic for hot rolling scheduling in compact strip production

This paper addresses a new hot rolling scheduling problem from the compact strip production process, which is the mainstream production technology that is used worldwide for sheet strips. The problem is modeled as a combination of two coupled sub-problems. One sub-problem is a sheet strip assignment problem that assigns sheet strips to rolling turns with the constraints of safe values of different gauge levels, and the other is a sheet strip sequencing problem that decides the rolling sequence for all of the sheet strips in a rolling turn to form a particular parabolic shape in thickness. To solve this hot rolling scheduling problem, we present a novel approach that consists of a sheet strip assignment heuristic and a sheet strip sequencing heuristic. The sheet strip assignment heuristic minimizes the number of virtual sheet strips by generating rolling turns according to the ordered sheet strips with maximum gauge level and their safe values. The sheet strip sequencing heuristic minimizes the average change of the thickness of adjacent sheet strips by arranging a certain number of duplicate sheet strips to the increasing stage of a rolling turn. Extensive experiments based on both synthetic and real-world instances from a compact strip production process show the effectiveness of the proposed two-stage heuristic in solving the hot rolling scheduling problem.     

A genetic algorithm for the generalised assignment problem

A new algorithm for the generalised assignment problem is described in this paper. The algorithm is adapted from a genetic algorithm which has been successfully used on set covering problems, but instead of genetically improving a set of feasible solutions it tries to genetically restore feasibility to a set of near-optimal ones. Thus it may be regarded as operating in a dual sense to the more familiar genetic approach. The algorithm has been tested on generalised assignment problems of substantial size and compared to an exact integer programming approach and a well-established heuristic approach.     

基于资源受限广义指派问题的分解启发式算法

资源受限广义指派问题(RGAP)是NP-难的,对RGAP问题给出一个分解启发式算法.通过分解目标函数及约束条件,把原问题分解成子问题的集合,并设计分解启发式算法找到该问题的满意解.最后,通过算例说明算法的有效性.     

A synthesis of assignment and heuristic solutions for vehicle routing with time windows

This paper proposes a three-stage method for the vehicle-routing problem with time window constraints (VRPTW). Using the Hungarian method the optimal customer matching for an assignment approximation of the VRPTW, which is a travel time-based relaxation that partially respects the time windows, is obtained. The assignment matching is transformed into feasible routes of the VRPTW via a simple decoupling heuristic. The best of these routes, in terms of travelling and vehicle waiting times, form part of the final solution, which is completed by the routes provided by heuristic methods applied to the remainder of the customers. The proposed approach is tested on a set of standard literature problems, and improves the results of the heuristic methods with respect to total travel time. Furthermore, it provides useful insights into the effect of employing optimal travel time solutions resulting from the assignment relaxation to derive partial route sets of the VRPTW.     

The equilibrium generalized assignment problem and genetic algorithm

The well-known generalized assignment problem (GAP) is to minimize the costs of assigning n jobs to m capacity constrained agents (or machines) such that each job is assigned to exactly one agent. This problem is known to be NP-hard and it is hard from a computational point of view as well. In this paper, follows from practical point of view in real systems, the GAP is extended to the equilibrium generalized assignment problem (EGAP) and the equilibrium constrained generalized assignment problem (ECGAP). A heuristic equilibrium strategy based genetic algorithm (GA) is designed for solving the proposed EGAP. Finally, to verify the computational efficiency of the designed GA, some numerical experiments are performed on some known benchmarks. The test results show that the designed GA is very valid for solving EGAP.     

An Algorithm for the Generalized Assignment Problem with Special Ordered Sets

The generalized assignment problem (GAP), the 0–1 integer programming (IP) problem of assigning a set of n items to a set of m knapsacks, where each item must be assigned to exactly one knapsack and there are constraints on the availability of resources for item assignment, has been further generalized recently to include cases where items may be shared by a pair of adjacent knapsacks. This problem is termed the generalized assignment problem with special ordered sets of type 2 (GAPS2). For reasonably large values of m and n the NP-hard combinatorial problem GAPS2 becomes intractable for standard IP software, hence there is a need for the development of heuristic algorithms to solve such problems. It will be shown how a heuristic algorithm developed previously for the GAP problem can be modified and extended to solve GAPS2. Encouraging results, in terms of speed and accuracy, have been achieved.     

求解系统可靠性优化中指派问题的启发式算法

本文回顾了系统可靠性优化中部件指派问题的研究,针对该类问题特点提出了一个新的启发式算法,该算法基于概率重要度来指派部件可靠度。文章最后给出了算例分析,并将算法结果与已有的算法和枚举法求得的最优解进行了比较。新的算法简单,而且效率非常高,可以在很短的计算时间内得到较好的求解效果,有效提高了复杂系统和大规模系统可靠性优化的计算效率。     

Capacitated lot sizing and scheduling with parallel machines and shared buffers: A case study in a packaging company

The aim of this work is to propose a solution approach for a capacitated lot sizing and scheduling real problem with parallel machines and shared buffers, arising in a packaging company producing yoghurt. The problem has been formulated as a hybrid Continuous Set-up and Capacitated Lot Sizing Problem (CSLP–CLSP). A new effective two stage optimisation heuristic based on the decomposition of the problem into a lot sizing problem and a scheduling problem has been developed. An assignment of mixture to buffers is made in the first stage, and therefore the corresponding orders are scheduled on the production lines by performing a local search. Computational tests have been performed on the real data provided by the company. The heuristic exhibits near-optimal solutions, all obtained in a very short computational time.     

Asymptotic Analysis of a Greedy Heuristic for the Multi-Period Single-Sourcing Problem: The Acyclic Case

The multi-period single-sourcing problem that we address in this paper can be used as a tactical tool for evaluating logistics network designs in a dynamic environment. In particular, our objective is to find an assignment of customers to facilities, as well as the location, timing and size of production and inventory levels, that minimizes total assignment, production, and inventory costs. We propose a greedy heuristic, and prove that this greedy heuristic is asymptotically optimal in a probabilistic sense for the subclass of problems where the assignment of customers to facilities is allowed to vary over time. In addition, we prove a similar result for the subclass of problems where each customer needs to be assigned to the same facility over the planning horizon, and where the demand for each customer exhibits the same seasonality pattern. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems. These results suggest that the greedy heuristic may be asymptotically optimal even for the cases that we were unable to analyze theoretically.     

A multi-period machine assignment problem

In this paper, a multi-period assignment problem is studied that arises as part of a weekly planning problem at mail processing and distribution centers. These facilities contain a wide variety of automation equipment that is used to cancel, sort, and sequence the mail. The input to the problem is an equipment schedule that indicates the number of machines required for each job or operation during the day. This result is then post-processed by solving a multi-period assignment problem to determine the sequence of operations for each machine. Two criteria are used for this purpose. The first is to minimize the number of startups, and the second is to minimize the number of machines used per operation.The problem is modeled as a 0–1 integer program that can be solved in polynomial time when only the first criterion is considered. To find solutions in general, a two-stage heuristic is developed that always obtains the minimum number of startups, but not necessarily the minimum number of machines per operation. In a comparative study, high quality solutions were routinely provided by the heuristic in negligible time when compared to a commercial branch-and-bound code (Xpress). For most hard instances, the branch-and-bound code was not able to even find continuous solutions within acceptable time limits.