Fuzzy weighted equilibrium multi-job assignment problem and genetic algorithm

In this paper, the equilibrium optimization problem is proposed and the assignment problem is extended to the equilibrium multi-job assignment problem, equilibrium multi-job quadratic assignment problem and the minimum cost and equilibrium multi-job assignment problem. Furthermore, the mathematical models of the equilibrium multi-job assignment problem and the equilibrium multi-job quadratic assignment problem with fuzzy parameters are formulated. Finally, a genetic algorithm is designed for solving the proposed programming models and some numerical examples are given to verify the efficiency of the designed algorithm.     

An alternative approach for unbalanced assignment problem via genetic algorithm

This paper presents an alternative approach using genetic algorithm to a new variant of the unbalanced assignment problem that dealing with an additional constraint on the maximum number of jobs that can be assigned to some agent(s). In this approach, genetic algorithm is also improved by introducing newly proposed initialization, crossover and mutation in such a way that the developed algorithm is capable to assign optimally all the jobs to agents. Computational results with comparative performance of the algorithm are reported for four test problems.     

Elitist genetic algorithm for assignment problem with imprecise goal

The objective of this research paper is to solve a generalized assignment problem with imprecise cost(s)/time(s) instead of precise one by elitist genetic algorithm (GA). Here, the impreciseness of cost(s)/time(s) has been represented by interval valued numbers, as interval valued numbers are the best representation than others like random variable representation with a known probability distribution and fuzzy representation. To solve these types of problems, an elitist GA has been developed with interval valued fitness function. In this developed GA, the existing ideas about the order relations of interval valued numbers have been modified from the point of view of two types of decision making viz., optimistic decision making and pessimistic decision making. This modified approach has been used in the selection process for selecting better chromosomes/individuals for the next generation and in finding the best as well as the worst chromosomes/individuals in each generation. Here two new crossover schemes and two new mutation schemes have been introduced. In order to maintain the feasibility with crossover operations, a repair algorithm has been suggested. Extensive comparative computational studies based on different parameters of our developed algorithm on one illustrative example have also been reported.     

Bees algorithm for generalized assignment problem

Bees algorithm (BA) is a new member of meta-heuristics. BA tries to model natural behavior of honey bees in food foraging. Honey bees use several mechanisms like waggle dance to optimally locate food sources and to search new ones. This makes them a good candidate for developing new algorithms for solving optimization problems. In this paper a brief review of BA is first given, afterwards development of a BA for solving generalized assignment problems (GAP) with an ejection chain neighborhood mechanism is presented. GAP is a NP-hard problem. Many meta-heuristic algorithms were proposed for its solution. So far BA is generally applied to continuous optimization. In order to investigate the performance of BA on a complex integer optimization problem, an attempt is made in this paper. An extensive computational study is carried out and the results are compared with several algorithms from the literature.     

Lagrangian relaxation guided problem space search heuristics for generalized assignment problems

We develop and test a heuristic based on Lagrangian relaxation and problem space search to solve the generalized assignment problem (GAP). The heuristic combines the iterative search capability of subgradient optimization used to solve the Lagrangian relaxation of the GAP formulation and the perturbation scheme of problem space search to obtain high-quality solutions to the GAP. We test the heuristic using different upper bound generation routines developed within the overall mechanism. Using the existing problem data sets of various levels of difficulty and sizes, including the challenging largest instances, we observe that the heuristic with a specific version of the upper bound routine works well on most of the benchmark instances known and provides high-quality solutions quickly. An advantage of the approach is its generic nature, simplicity, and implementation flexibility.     

The generalized assignment problem with flexible jobs

The Generalized Assignment Problem (GAP) seeks an allocation of jobs to capacitated resources at minimum total assignment cost, assuming a job cannot be split among multiple resources. We consider a generalization of this broadly applicable problem in which each job must not only be assigned to a resource, but its resource consumption must also be determined within job-specific limits. In this profit-maximizing version of the GAP, a higher degree of resource consumption increases the revenue associated with a job. Our model permits a job’s revenue per unit resource consumption to decrease as a function of total resource consumption, which allows modeling quantity discounts. The objective is then to determine job assignments and resource consumption levels that maximize total profit. We develop a class of heuristic solution methods, and demonstrate the asymptotic optimality of this class of heuristics in a probabilistic sense.     

The generalized assignment problem: Valid inequalities and facets

Three classes of valid inequalities based upon multiple knapsack constraints are derived for the generalized assignment problem. General properties of the facet defining inequalities are discussed and, for a special case, the convex hull is completely characterized. In addition, we prove that a basic fractional solution to the linear programming relaxation can be eliminated by a facet defining inequality associated with an individual knapsack constraint.Partial financial support under NSF grant #CCR-8812736.Partial financial support under NSF grant #DMS-8606188.     

An algorithm for the generalized quadratic assignment problem

This paper reports on a new algorithm for the Generalized Quadratic Assignment problem (GQAP). The GQAP describes a broad class of quadratic integer programming problems, wherein M pair-wise related entities are assigned to N destinations constrained by the destinations’ ability to accommodate them. This new algorithm is based on a Reformulation Linearization Technique (RLT) dual ascent procedure. Experimental results show that the runtime of this algorithm is as good or better than other known exact solution methods for problems as large as M=20 and N=15. Current address of P.M. Hahn: 2127 Tryon Street, Philadelphia, PA 19146-1228, USA.     

An approximation algorithm for the generalized assignment problem

The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly one machine; processing jobj on machinei requires timep _ij and incurs a cost ofc _ij ; each machinei is available forT _i time units, and the objective is to minimize the total cost incurred. Our main result is as follows. There is a polynomial-time algorithm that, given a valueC, either proves that no feasible schedule of costC exists, or else finds a schedule of cost at mostC where each machinei is used for at most 2T _i time units.We also extend this result to a variant of the problem where, instead of a fixed processing timep _ij , there is a range of possible processing times for each machine—job pair, and the cost linearly increases as the processing time decreases. We show that these results imply a polynomial-time 2-approximation algorithm to minimize a weighted sum of the cost and the makespan, i.e., the maximum job completion time. We also consider the objective of minimizing the mean job completion time. We show that there is a polynomial-time algorithm that, given valuesM andT, either proves that no schedule of mean job completion timeM and makespanT exists, or else finds a schedule of mean job completion time at mostM and makespan at most 2T. Research partially supported by an NSF PYI award CCR-89-96272 with matching support from UPS, and Sun Microsystems, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.Research supported in part by a Packard Fellowship, a Sloan Fellowship, an NSF PYI award, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

Compounded genetic algorithms for the quadratic assignment problem

We introduce the compounded genetic algorithm. We propose to run a quick genetic algorithm several times as Phase 1, and compile the best solutions in each run to create a starting population for Phase 2. This new approach was tested on the quadratic assignment problem with very good results.     

A simplex-based labelling algorithm for the linear fractional assignment problem

This paper constructs an algorithm to solve the fractional assignment problem. Algorithms that are currently used are mostly based on parametric approaches and must solve a sequence of optimization procedures. They also neglect the difficulties caused by degeneracy. The proposed algorithm performs optimization once and overcomes degeneracy. The main features of the algorithm are an effective initial heuristic approach, a simple labelling procedure and an implicit primal-dual schema. A numerical example is presented and demonstrates that the proposed algorithm is easy to apply. Computational results are compared with those from other developed methods. The results show that the proposed algorithm is efficient.     

A labeling algorithm for the sensitivity ranges of the assignment problem

In view of the simplex-type algorithm, the assignment problem is inherently highly degenerate. It may be the optimal basis has changed, but the optimal assignment is unchanged when parameter variation occurs. Degeneracy then makes sensitivity analysis difficult, as well as makes the classical Type I range, which identifies the range the optimal basis unchanged, impractical. In this paper, a labeling algorithm is proposed to identify two other sensitivity ranges – Type II range and Type III range. The algorithm uses the reduced cost matrix, provided in the final results of most solution algorithms for AP, to determine the Type II range which reflects the stability of the current optimal assignment. Thus, the algorithm generates a streamlined situation from searching the optimal solution until performing the sensitivity analysis of the assignment problem. The Type III range, reflecting the flexibility of optimal decision making, can be obtained immediately after the Type II range is determined. Numerical examples are presented to demonstrate the algorithm.     

An efficient cost scaling algorithm for the assignment problem

The cost scaling push-relabel method has been shown to be efficient for solving minimum-cost flow problems. In this paper we apply the method to the assignment problem and investigate implementations of the method that take advantage of assignment's special structure. The results show that the method is very promising for practical use.This author's research was supported in part by ONR Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC and 3M, and a grant from the Powell Foundation.This author's research was supported by the above-mentioned ONR and NSF grants.     

Multistate components assignment problem with optimal network reliability subject to assignment budget

The typical assignment problem for finding the optimal assignment of a set of components to a set of locations in a system has been widely studied in practical applications. However, this problem mainly focuses on maximizing the total profit or minimizing the total cost without considering component’s failure. In practice, each component should be multistate due to failure, partially failure, or maintenance. That is, each component has several capacities with a probability distribution and may fail. When a set of multistate components is assigned to a system, the system can be treated as a stochastic-flow network. The network reliability is the probability that d units of homogenous commodity can be transmitted through the network successfully. The multistate components assignment problem to maximize the network reliability is never discussed. Therefore, this paper focuses on solving this problem under an assignment budget constraint, in which each component has an assignment cost. The network reliability under a components assignment can be evaluated in terms of minimal paths and state-space decomposition. Subsequently an optimization method based on genetic algorithm is proposed. The experimental results show that the proposed algorithm can be executed in a reasonable time.     

Single row facility layout problem using a permutation-based genetic algorithm

In this paper, a permutation-based genetic algorithm (GA) is applied to the NP-hard problem of arranging a number of facilities on a line with minimum cost, known as the single row facility layout problem (SRFLP). The GA individuals are obtained by using some rule-based as well as random permutations of the facilities, which are then improved towards the optimum by means of specially designed crossover and mutation operators. Such schemes led the GA to handle the SRFLP as an unconstrained optimization problem. In the computational experiments carried out with large-size instances of sizes from 60 to 80, available in the literature, the proposed GA improved several previously known best solutions.     

An algorithm based on the generalized D-gap function for equilibrium problems

The equilibrium problem (EP) can be reformulated as an unconstrained minimization problem through the generalized D-gap function. In this paper, we propose an algorithm for minimizing the problem and analyze some convergence properties of the proposed algorithm. Under some reasonable conditions, we show that the iteration sequence generated by the algorithm is globally convergent and converges to a solution to the EP and the generalized D-gap function provides a global error bound for the algorithm.     

An improved origin-based algorithm for solving the combined distribution and assignment problem

This paper is to further study the origin-based (OB) algorithm for solving the combined distribution and assignment (CDA) problem, where the trip distribution follows a gravity model and the traffic assignment is a user-equilibrium model. Recently, the OB algorithm has shown to be superior to the Frank–Wolfe (FW) algorithm for the traffic assignment (TA) problem and better than the Evans’ algorithm for the CDA problem in both computational time and solution accuracy. In this paper, a modified origin–destination (OD) flow update strategy proposed by Huang and Lam [Huang, H.J., Lam, W.H.K., 1992. Modified Evans’ algorithms for solving the combined trip distribution and assignment problem. Transportation Research B 26 (4), 325–337] for CDA with the Evans’ algorithm is adopted to improve the OB algorithm for solving the CDA problem. Convergence proof of the improved OB algorithm is provided along with some preliminary computational results to demonstrate the effect of the modified OD flow update strategy embedded in the OB algorithm.     

An extended assignment problem considering multiple inputs and outputs

The existing assignment problems for assigning n jobs to n individuals are limited to the considerations of cost or profit incurred by each possible assignment. However, in real applications, various inputs and outputs are usually concerned in an assignment problem, such as a general decision-making problem. This paper develops a procedure for resolving assignment problems with multiple incommensurate inputs and outputs for each possible assignment. The concept of the relative efficiency in using various resources, instead of cost or profit, is adopted for each possible assignment of the problem. Data envelopment analysis (DEA) is employed in this paper to measure the efficiency of one assignment relative to that of the others according to a set of decision-making units. A composite efficiency index, consisting of two kinds of relative efficiencies under different comparison bases, is defined to serve as the performance measurement of each possible assignment in the problem formulation. A mathematical programming model for the extended assignment problem is proposed, which is then expressed as a classical integer linear programming model to determine the assignments with the maximum efficiency. A numerical example is used to demonstrate the approach.     

The stochastic generalised assignment problem with Bernoulli demands

This paper deals with the Stochastic Generalised Assignment problem. It presents several models for the special case when demands are independent and Bernoulli distributed. Each model designs an assignment structure before the demands are known. Two policies are considered to handle infeasibilities in particular instances of the demands vector. Model performances are compared under both policies.