China
Africa
Explore chapters and articles related to this topic
Integer Programming
Published in Michael W. Carter, Camille C. Price, Ghaith Rabadi, Operations Research, 2018
Michael W. Carter, Camille C. Price, Ghaith Rabadi
The generalized assignment problem is a simple extension in which every job must be assigned to one employee, but each employee has the capacity to perform more than one job. In particular, suppose that each employee, j, has a limited amount of time, (bj hours) available, and that job i will take employee j a total of aij hours. Then, the generalized assignment problem can be formulated as: minimize∑i∑jcijxijsubject to∑jxij=1 for all i=1, …,m∑iaijxij≤bj for all j=1,…,nxij=0 or 1 for all i, j
Energy-aware task allocation strategy for multi robot system
Published in International Journal of Modelling and Simulation, 2022
In this paper, the task allocation is formulated as the Classical Assignment Problem (CAP) which can be considered as an instance of the Generalized Assignment Problem (GAP). The GAP is well known in Combinatorial optimization and is extensively studied [22,23,49]. The GAP is an NP-Hard problem [50], yet some GAP variation, such as the CAP, can be solved with exact methods using polynomial time algorithms such as branch boundary algorithm, Hungarian algorithm, simplex methods, and Lagrangian relaxation algorithms [51,52]. Although exact methods can guarantee optimal allocation, they require a lot of computation. In most real-time applications, the need for strategies that would ensure rapid and effective task allocation is more critical than producing an exact optimal solution [32,53]. Heuristics, such as the Greedy algorithm, are well known to provide a quick suboptimal solution. However, they can be myopic at the time and stuck in local optima. Thus, the use of metaheuristic is more convenient.
Exact Methods for Multi-Objective Integer Nonlinear Programming
Published in Cybernetics and Systems, 2022
The generalized assignment problem (GAP), a well-known integer optimization problem, involves obtaining the minimum cost assignment of a set of jobs to a set of agents. Each job must be assigned to one agent. The total resources required by any agent cannot exceed its available capacity (Osman 1995). In this article, multi-objective integer nonlinear GAP (MOINL-GAP) is used as a test problem for algorithm performance.