Search

Summary: The spectral efficiency of a cellular network can be increased significantly by allowing spatial reuse of its spectrum by an underlay device‐to‐device (D2D) network. In an underlay D2D network, devices in close vicinity are allowed to establish low‐power direct links with little to no involvement of the base station. In order to increase the spectral efficiency and the number of devices with channel access, multiple D2D pairs may transmit in each cellular channel. Additionally, each pair can be allowed to utilize multiple channels to transmit so as to maximize the D2D network capacity. This multiple‐pair multiple‐channel (MPMC) strategy is quite appealing but is limited by the resultant additional aggregate interference and the inherent complexity, hence necessitating the need for a fast and reliable channel allocation scheme. This work proposes a polynomial‐time iterative Hungarian assignment with feedback (IHAF) algorithm for multiple channel allocations amongst multiple D2D pairs that increases the D2D network capacity manifold while maintaining the desired minimum capacity for each cellular user. [ABSTRACT FROM AUTHOR]

Copyright of GeSec: Revista de Gestao e Secretariado is the property of Sindicato das Secretarias e Secretarios do Estado de Sao Paulo (SINSESP) and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In practice, allocating tasks to resources is often tackled in (near) real-time due to the latency of the task information and sudden task arrivals into a system. Therefore, the problem must be solved within a very short time budget, when tasks are urgent or idle resources are critical to the system's performance. Local search algorithms could be a good solution to this issue. These algorithms usually focus the search on limited solution areas by applying local updates on an incumbent solution. To investigate the feasibility and performance of applying a local search algorithm to resource allocation, a special case of the Generalized Assignment Problem (GAP) is modelled, where task profits are independent of the resources assigned and resources' capacities are identical. Then the performance of a local search algorithm to the target problems is examined empirically, characterizing the features of the GAP that make the problem hard for heuristics. [ABSTRACT FROM AUTHOR]

The development of Multi-access edge computing (MEC) has resulted from the requirement for supporting next generation mobile services, which need high capacity, high reliability and low latency. The key issue in such MEC architectures is to decide which edge nodes will be employed for serving the needs of the different end users. Here, we take a fresh look into this problem by focusing on the minimization of migration events rather than focusing on maximizing usage of resources. This is important because service migrations can create significant service downtime to applications that need low latency and high reliability, in addition to increasing traffic congestion in the underlying network. This paper introduces a priority induced service migration minimization (PrISMM) algorithm, which aims at minimizing service migration for both high and low priority services, through the use of Markov decision process, learning automata and combinatorial optimization. We carry out extensive simulations and produce results showing its effectiveness in reducing the mean service downtime of lower priority services and the mean admission time of the higher priority services. [ABSTRACT FROM AUTHOR]

This work is motivated by a memory allocation problem (MAP) in an embedded system which is modeled as a generalized assignment problem (GAP) with side constraints. Thus, this paper aims to design a fast and sufficiently accurate method for GAP that will be used in future research to obtain a solution for MAP. Since this solution barely satisfies the conflict constraints, it will be repaired and then improved using local search. In the current research, the proposed method for GAP combines data reduction, a MIP solver, and iterated local search (ILS). The generic data reduction procedure is based on useful information provided by applying subgradient optimization to the Lagrangian relaxation of the knapsack constraints. In practice, it can eliminate up to 96 % of GAP variables. The reduced GAP left by this procedure is small and sparse. Furthermore, its optimal solution can be easily extended to an optimal or near-optimal solution of GAP. An ILS metaheuristic is designed for solving the reduced GAP and the entire method is tested on a widely used benchmark of large and difficult instances. Its comparison with recently published methods shows that it is competitive in terms of solution quality; it is also by far the fastest. [ABSTRACT FROM AUTHOR]

The emergence of GPU-CPU heterogeneous architecture has led to a significant paradigm shift in parallel programming. How to effectively implement Parallel Genetic Algorithm (GA) in these environments has become one of the current hot issues. GA's calculation and operators are closely related to specific problems, thereby significantly affecting the acceleration method of GA algorithms. The Generalized Assignment Problem (GAP) is a classic NP-hard combinatorial optimization problem. The more widely used genetic algorithms to solve the GAP in the CPU are difficult to be parallelized in a GPU environment due to severe data dependencies. To address this problem, two algorithms suitable for the implementation on the GPU are proposed, namely RPE algorithm and NNE algorithm, which obtain significant performance speedup by alleviating data dependencies and mutually exclusive synchronization overheads. At the same time, considering the new GPU architecture features and programming models, three different granular implementations of parallel genetic algorithms to solve the GAP are proposed, namely GPGA thread , GPGA warpsp and GPGA cgroup , by utilizing the warp-specialization technology and the cooperative group mechanism. GPGA series algorithms obtain better solution quality and very significant performance improvements compared with Serial GA, GTS (the GPU-CPU hybrid implementation of Scatter Search with Tabu lists) and Lagrange Relaxation algorithm on a CPU by solving 16 typical large-scale GAP instances. [ABSTRACT FROM AUTHOR]

This paper studies the problem of energy efficiency (EE) maximization via user association, power, and backhaul (BH) flow control in the downlink of millimeter wave BH heterogeneous networks. This problem is mathematically formulated as a mixed-integer non-linear program, which is non-convex. To get a tractable solution, the initial problem is separated into two sub-problems and optimized sequentially. The first is a joint user association and power control sub-problem for the access network (AN) (AN sub-problem). The second is a joint flow and power control sub-problem for the BH network (BH sub-problem). While the BH sub-problem is a convex optimization problem and hence can be efficiently solved, the AN sub-problem assumes the form of a generalized assignment problem, which is known to be NP-hard. To that end, we utilize Lagrangian decomposition to propose two polynomial time solution techniques that obtain a high-quality solution for the AN sub-problem. The first, referred to as Technique A, uses dynamic programming, the subgradient method, and a heuristic. The second, named Technique B, uses the multiplier adjustment method, the sorting algorithm, and a heuristic. Simulation results are used to demonstrate the effectiveness of the proposed energy efficient user association, power, and BH flow control algorithms as compared with benchmark user association schemes that incorporate the BH sub-problem algorithm, in terms of the total AN power, BH power, and overall network (AN plus BH) EE. The computational complexity and practical implementation of the proposed algorithms are discussed.

We show that the core of a generalized assignment problem satisfies two types of stability properties. First, the core is the unique stable set defined using the weak domination relation when outcomes are restricted to individually rational and pairwise feasible ones. Second, the core is the unique stable set with respect to a sequential domination relation that is defined by a sequence of weak domination relations that satisfy outsider independence. An equivalent way of stating this result is that the core satisfies the property commonly stated as the existence of a path to stability. These results add to the importance of the core in an assignment problem where agents' preferences may not be quasilinear. [ABSTRACT FROM AUTHOR]

The paper is motivated by real problems concerning tasks assignment to workers in medium-sized upholstered furniture plants managed using the Demand-Driven Manufacturing. Although the methodology was developed for furniture plants it can be applied to other types of production plants. We involve competence coefficients, which describe the level of the worker's skills or capabilities to perform a specific task. The competence coefficients are also used to block the possibility of assigning the given task to a worker that has no skills to do it. Additionally, we involve a dummy worker to the model which guarantees the existence of a solution to the problem. We present and discuss Integer Linear Programming Models for the posted problem that are closely related to the Generalized Assignment Problem. We also discuss the potential use of the presented methodology to solve real-life problems related to production management. [ABSTRACT FROM AUTHOR]

Efficient planning and management of the workforce resources is one of the most essential requirements for the companies operating in the service sector. For banks, a large number of transactions coming to Central Operations Department from the branches or directly from the customers and their aim is to provide the best operational service with the highest efficiency with the limited workforce resources in the departments. In this study, a real assignment problem was discussed and the problem was considered as Generalized Assignment Problem. For the solution of the problem, related algorithms were listed and examined in the literature survey section. Then, a two-step method is proposed. First step prioritizes the task coming to the system by considering the customer types, service level agreement (SLA) times, cut-off times, task type. In the second step, a multi-objective mathematical model was developed to assign task to employee groups. A preference based optimization method called Linear Physical Programming (LPP) is used to solve the model. Afterward, proposed model was tested on real banking data. For all the tests, GAMS was used as a solver. Results show that proposed model gave better results compared with current situation. With the proposed solution method, the workloads of the profile groups working above their capacity were transferred to other profile groups with idle capacity. Thus, the capacity utilization rates of the profile groups were more balanced and the minimum capacity utilization rate was calculated as 41%.

Efficient planning and management of the workforce resources is one of the most essential requirements for the companies operating in the service sector. For banks, a large number of transactions comes to Central Operations Department from the branches or directly from the customers and their aim is to provide the best operational service with the highest efficiency with the limited workforce resources in the departments. In this study, a real assignment problem was discussed and the problem was considered as Generalized Assignment Problem. For the solution of the problem, related algorithms were listed and examined in the literature survey section. Then, a two-step method is proposed. First step prioritizes the task coming to the system by considering the customer types, service level agreement (SLA) times, cut-off times, task type. In the second step, a multi-objective mathematical model was developed to assign task to employee groups. A preference based optimization method called Linear Physical Programming (LPP) is used to solve the model. Afterward, proposed model was tested on real banking data. For all the tests, GAMS was used as a solver. Results show that proposed model gave better results compared with current situation. With the proposed solution method, the workloads of the profile groups working above their capacity were transferred to other profile groups with idle capacity. Thus, the capacity utilization rates of the profile groups were more balanced and the minimum capacity utilization rate was calculated as 41%. [ABSTRACT FROM AUTHOR]

This paper presents a method for work team and logistics formation. The proposed method solves a mathematical model in binary variables 0/1 developed based on the generalized assignment model in order to minimize the cost of transportation and form work teams with a pre-established number of agents. The corresponding program was written in-Solver and tested in an outsourced service provider, which operates in more than 200 Brazilian cities.

Highlights • A human resource planning for a home healthcare system based on the SGAP formulation. • Developing a planning for a duration of multiple days considering the off-days. • An optimization model to integrate the Assignment and Vehicle Routing problems. • A matheuristic based on the decomposition of the formulation to simplify the model. • A statistical analysis to evaluate the proposed optimization approaches. Abstract To model a home health care planning problem by classical VRP and AP formulation, the dimensions of the problem are: 1. The staff, 2. The patients, 3. The routes (sequence of the patients for each staff member). In this study, we present an extension of the home health care planning problem by adding the extra dimension of time so that the staff are not only assigned to the patients, but they are also assigned to daily periods. The scope of the planning problem extends to multiple days in which the patient required services vary from one day to another. Hence, the problem concerns a sequence of schedules (one schedule for each day) for the staff members. This variant of the home health care planning problem is modeled mathematically by employing the sequencing generalized assignment formulation and solved by applying the Gurobi mixed-integer solver. Considering that the studied combinatorial optimization is NP-complete, a matheuristic approach based on the decomposition of the formulation is proposed in this research to simplify the mathematical model and reduce the computational time needed to solve the problem. The numerical experiences and statistical analysis show that our matheuristic approach solves 90% of the instances to optimality with a significant reduction in the computational times. [ABSTRACT FROM AUTHOR]

Generalized assignment problem (GAP) considers finding minimum cost assignment of n tasks to m agents provided each task should be assigned to one agent only. In this study, a new Genetic Algorithm (GA) with some new methods has been proposed to solve GAPs. The agent-based crossover is based on the concept of dominant gene in genotype science and increases the fertility rate of the feasible solutions. The solutions are classified as infeasible, feasible and mature with reference to their conditions. The new local searches provide not only feasibility in high diversity but high profitability for the solutions. A solution is not given up through maturation- based replacement until it reaches its best. The computational results show that the agent-based crossover has much higher fertility rate than classical crossover. Finally, the proposed GA creates either optimal or near-optimal solutions. [ABSTRACT FROM AUTHOR]

Abstract This paper uses operations research (OR) to investigate inpatient care work planning decisions from the perspective of a single healthcare provider in a hospital unit. While there has been considerable research on the modeling and analysis of healthcare delivery systems to support medium- to long-term decisions (e.g., daily operating room scheduling, weekly nurse scheduling), there is little research focusing on decisions made at the operational level by front-line providers. At this stage, resources have been allocated, personnel have been scheduled, and a set of patients with specific demands needs to be cared for in a safe, effective, efficient, timely, patient-centered, and equitable manner. It is often the responsibility of the actual providers to plan, execute, and adjust their workflow based on their knowledge and experience. This paper describes short-term work planning decisions made by front-line healthcare workers and illustrates how OR can support the analysis of such decisions. Research questions that motivate the use of OR in the design and analysis of inpatient care work are discussed. [ABSTRACT FROM AUTHOR]

We study packing linear programs (LPs) in an online model where the columns are presented to the algorithm in random order. This natural problem was investigated in various recent studies motivated, e.g., by online ad allocations and yield management, where rows correspond to resources and columns to requests specifying demands for resources. Our main contribution is a 1 - O(√(log d)=B)-competitive online algorithm. Here d denotes the column sparsity, i.e., the maximum number of resources that occur in a single column, and B denotes the capacity ratio B, i.e., the ratio between the capacity of a resource and the maximum demand for this resource. In other words, we achieve a (1 - ε)-approximation if the capacity ratio satisfies B = (log d/e²), which is known to be the best possible for any (randomized) online algorithms. Our result improves exponentially on previous work with respect to the capacity ratio. In contrast to existing results on packing LP problems, our algorithm does not use dual prices to guide the allocation of resources over time. Instead, the algorithm simply solves, for each request, a scaled version of the partially known primal program and randomly rounds the obtained fractional solution to obtain an integral allocation for this request. We show that this simple algorithmic technique is not restricted to packing LPs with large capacity ratio of order (log d), but also yields close-to-optimal competitive ratios if the capacity ratio is bounded by a constant. In particular, we prove an upper bound on the competitive ratio of Ω(d-1=(B-1)) for any B ≥ 2. In addition, we show that our approach can be combined with VCG payments and obtain an incentive-compatible (1 - ε)-competitive mechanism for packing LPs with B = (log d/e²), where m is the number of constraints. Finally, we apply our technique to the generalized assignment problem for which we obtain the first online algorithm with competitive ratio O(1). [ABSTRACT FROM AUTHOR]

Many combinatorial optimisation problems are NP-Hard. Yet in practice high quality solutions are often obtained by (meta)heuristics. These work well in some cases, but not in others, indicating a potential for algorithm selection. In this extended abstract is discussed how to apply algorithm selection to a combinatorial optimisation problem and which challenges arise when doing so. The generalised assignment problem is used as case study. [ABSTRACT FROM AUTHOR]

We proposed and created a methodology to solve a real-world problem, which is a special case of the generalized assignment problem. The problem consists of assigning drivers to harvesters, which will then be assigned to harvest sugarcane in order to maximize daily profit. A set of drivers have various levels of experience. Therefore, a different capability to harvest sugarcane leads to a range of daily wages. Each harvester has different operating years and engine size, which affects its fuel consumption rate and capacity to harvest sugarcane, respectively. Assigning a worker to a harvester can improve the fuel consumption and efficiency of the harvester. We developed a mathematical model to reflect this problem and to solve it to find the maximum outcome using Lingo v.11 commercial optimization software. Since Lingo v.11 is limited to solving only small-size test instances, for medium to large test instances, four modified differential evolution (MDE) algorithms were used to solve the problem: MDE-1, MDE-2, MDE-3, and MDE-4. MDE-2 was found to be the best proposed heuristics because it has intensification and diversification ability. MDE has been tested with the case study. We tried to increase the daily profit by implementing three strategies: (1) change all harvesters that are more than five years old, (2) train drivers to reach maximum capacity, and (3) a combination of 1 and 2. Each strategy has a different investment. The breakeven point (number of days) to return the investment was calculated from the increase of daily profit. The computational results show that strategy 2 is the best because it has the quickest rate of investment return rate. However, this strategy has a disadvantage, since it is possible that drivers may leave the company if they have been highly trained. Moreover, strategy 1 has an acceptable break-even point at 392 days.

Emerging transportation network services, such as customized buses, hold the promise of expanding overall traveler accessibility in congested metropolitan areas. A number of internet-based customized bus services have been planned and deployed for major origin-destination (OD) pairs to/from inner cities with limited physical road infrastructure. In this research, we aim to develop a joint optimization model for addressing a number of practical challenges for providing flexible public transportation services. First, how to maintain minimum loading rate requirements and increase the number of customers per bus for the bus operators to reach long-term profitability. Second, how to optimize detailed bus routing and timetabling plans to satisfy a wide range of specific user constraints, such as passengers’ pickup and delivery locations with preferred time windows, through flexible decision for matching passengers to bus routes. From a space-time network modeling perspective, this paper develops a multi-commodity network flow-based optimization model to formulate a customized bus service network design problem so as to optimize the utilization of the vehicle capacity while satisfying individual demand requests defined through space-time windows. We further develop a solution algorithm based on the Lagrangian decomposition for the primal problem and a space-time prism based method to reduce the solution search space. Case studies using both the illustrative and real-world large-scale transportation networks are conducted to demonstrate the effectiveness of the proposed algorithm and its sensitivity under different practical operating conditions. [ABSTRACT FROM AUTHOR]

In the Generalized Assignment Problem (GAP), tasks must be allocated to machines with limited resources, in order to minimize processing costs. This problem has several industrial applications and often appears as a substructure in other combinatorial optimization problems. We propose a hybrid method inspired by Scatter Search metaheuristic, that efficiently generates a pool of solutions using a Tabu list criteria and an Ejection Chain mechanism. Common characteristics are extracted from the pool and solutions are combined by exploring a restricted search space, as a Binary Programming (BP) model. This method was implemented as a parallel approach to run in a Graphics Processing Unit (GPU). Experimental results show that the proposed method is very competitive to the algorithms found in the literature. On average, a gap of 0.09% is obtained over a set of 45 instances, when compared to lower bounds. Due to the integration of the method with an exact BP solver, it was capable of proving the optimality of small size instances, also finding new best known solutions for 21 instances. In terms of computational times, the proposed method performs on average 8 times faster than literature, also indicating that the proposed approach is scalable and robust for practical applications. [ABSTRACT FROM AUTHOR]

Many central examinations are performed nationwide in Turkey. These examinations are held simultaneously throughout Turkey. Examinees attempt to arrive at the examination centers at the same time and they encounter problems such as traffic congestion, especially in metropolises. The state of mind that this situation puts them into negatively affects the achievement and future goals of the test takers. Our solution to minimize the negative effects of this issue is to assign the test takers to closest examination centers taking into account the capacities of examination halls nearby. This solution is a special case of the generalized assignment problem (GAP). Since the scale of the problem is quite large, we have focused on heuristic methods. In this study, a modified genetic algorithm (GA) is used for the solution of the problem since the classical GA often generates infeasible solutions when it is applied to GAPs. A new method, named nucleotide exchange, is designed in place of the crossover method. The designed method is run between the genes of a single parent chromosome. In addition to the randomness, the consciousness factor is taken into consideration in the mutation process. With this new GA method, results are obtained successfully and quickly in large-sized data sets. [ABSTRACT FROM AUTHOR]