Search

In the online facility assignment problem OFA (k , { c i } i = 1 k) , there exist k servers s 1 , ... , s k on a metric space where each s i has an integer capacity c i and a request arrives one-by-one. The task of an online algorithm is to irrevocably match a current request with one of the servers with vacancies before the next request arrives. As special cases for OFA (k , { c i } i = 1 k) , we consider OFA (k , { c i } i = 1 k) on a line , which is denoted by OFAL (k , { c i } i = 1 k) and OFAL eq (k , { c i } i = 1 k) , where the latter is the case of OFAL (k , { c i } i = 1 k) with equidistant servers. In this paper, we perform the competitive analysis for the above problems. As a natural generalization of the greedy algorithm grdy, we introduce a class of algorithms called MPFS (Most Preferred Free Servers) and show that any MPFS algorithm has the capacity-insensitive property, i.e., for any MPFS algorithm alg for OFA (k , { c i } i = 1 k) , if alg is c -competitive when c 1 = ⋯ = c k = 1 , then alg is c -competitive for general { c i } i = 1 k . By applying the capacity-insensitive property of the greedy algorithm grdy, we derive the matching upper and lower bounds 4 k − 5 on the competitive ratio of grdy for OFAL eq (k , { c i } i = 1 k). To investigate the capability of MPFS algorithms, we show that the competitive ratio of any MPFS algorithm alg for OFAL eq (k , { c i } i = 1 k) is at least 2 k − 1. Then, we propose a new MPFS algorithm idas (Interior Division for Adjacent Servers) for OFAL (k , { c i } i = 1 k) and show that the competitive ratio of idas for OFAL eq (k , { c i } i = 1 k) is at most 2 k − 1 , i.e., idas for OFAL eq (k , { c i } i = 1 k) is best possible in all the MPFS algorithms. We also give numerical experiments to investigate the performance of idas and grdy and show that idas performs better than grdy for distribution of request sequences with locality. [ABSTRACT FROM AUTHOR]

In this paper, we present a variable sample-size operator extrapolation algorithm for solving a class of stochastic mixed variational inequalities. One distinctive feature of our algorithm is that it updates a single search sequence by solving a prox-mapping subproblem and computing an evaluation of the expected mapping at each iteration and hence it may significantly reduce computation load. In particular, the iteration sequence generated by our algorithm always belongs to the feasible region. We show that, under some moderate conditions, the proposed algorithm can achieve O (1 / T) ergodic convergence rate in terms of the expected restricted gap function, where T denotes the number of iterations. We derive some results related to the convergence rate of the Bregman distance between iterates and solutions, the iteration complexity, and the oracle complexity for the proposed algorithm when the sample size increases at a geometric rate. We also investigate the sublinear convergence rate in terms of the residual function under the generalized monotonicity condition. Numerical experiments on stochastic network game, stochastic sparse traffic assignment problems and sparse classification problem indicate that the proposed algorithm is promising compared with some existing algorithms. [ABSTRACT FROM AUTHOR]

Ride-pooling, which accommodates multiple passenger requests in a single trip, has the potential to substantially enhance the throughput of mobility-on-demand (MoD) systems. This paper investigates MoD systems that operate mixed fleets composed of "basic supply" and "augmented supply" vehicles. When the basic supply is insufficient to satisfy demand, augmented supply vehicles can be repositioned to serve rides at a higher operational cost. We formulate the joint vehicle repositioning and ride-pooling assignment problem as a two-stage stochastic integer program, where repositioning augmented supply vehicles precedes the realization of ride requests. Sequential ride-pooling assignments aim to maximize total utility or profit on a shareability graph: a hypergraph representing the matching compatibility between available vehicles and pending requests. Two approximation algorithms for midcapacity and high-capacity vehicles are proposed in this paper; the respective approximation ratios are 1 / p 2 and (e − 1) / (2 e + o (1)) p ln p , where p is the maximum vehicle capacity plus one. Our study evaluates the performance of these approximation algorithms using an MoD simulator, demonstrating that these algorithms can parallelize computations and achieve solutions with small optimality gaps (typically within 1%). These efficient algorithms pave the way for various multimodal and multiclass MoD applications. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. Funding: This work was supported by the National Science Foundation [Grants CCF-2006778 and FW-HTF-P 2222806], the Ford Motor Company, and the Division of Civil, Mechanical, and Manufacturing Innovation [Grants CMMI-1854684, CMMI-1904575, and CMMI-1940766]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2021.0349. [ABSTRACT FROM AUTHOR]

This study focuses on the load balancing of the transactions in the blockchain. The problem is how to assign these transactions to the blocks. The objective is to guarantee a load balancing of the workload in the time of blocks. The proposed problem is an NP-hard one. To face the hardness of the studied problem, the challenge is to develop algorithms that solve the problem approximately. Finding an approximate solution is a real challenge. In this paper, nine algorithms are proposed. These algorithms are based on the dispatching-rules method, randomization approach, clustering algorithms, and iterative method. The proposed algorithms return approximate solutions in a remarkable time. In addition, in this paper, a novel architecture composed of blocks is proposed. This architecture adds the component "Balancer". This component is responsible to call the best-proposed algorithm and solve the scheduling problem in a polynomial time. In addition, the proposed work helps users to solve the problem of big data concurrency. These algorithms are coded and compared. The performance of these algorithms is tested over three classes of instances. These classes are generated based on uniform distribution. The total number of instances tested is 1350. The average gap, execution time, and the percentage of the best-reached value are used as metrics to measure the performance of the proposed algorithms. Experimental results show the performance of these algorithms and a comparison between them is discussed. The experimental results show that the best algorithm is best-mi-transactions iterative multi-choice with 93.9% in an average running time of 0.003 s. [ABSTRACT FROM AUTHOR]

In the paper, we consider a generalization of the classical assignment problem, which is called the constrained assignment problem with bounds and penalties (CA-BP). Specifically, given a set of machines and a set of independent jobs, each machine has a lower and upper bound on the number of jobs that can be executed, and each job must be either executed on some machine with a given processing time or rejected with a penalty that we must pay for. No job can be executed on more than one machine. We aim to find an assignment scheme for these jobs that satisfies the constraints mentioned above. The objective is to minimize the total processing time of executed jobs as well as the penalties from rejected jobs. The CA-BP is related to some practical applications such as edge computing, which involves selecting tasks and processing them on the edge servers of an internet network. As a result, a motivation of this study is to improve the efficiency of internet networks by limiting the lower bound of the number of objects processed by each edge server. Our main contribution is modifying the previous network flow algorithms to satisfy the lower capacity constraints, for which we design two exact combinatorial algorithms to solve the CA-BP. Our methodologies and results bring novel perspectives into other research areas related to the assignment problem. [ABSTRACT FROM AUTHOR]

We consider the incremental subgradient algorithm employing dynamic step sizes for minimizing the sum of a large number of component convex functions. The dynamic step size rule was firstly introduced by Goffin and Kiwiel [Math. Program., 1999, 85(1): 207‐211] for the subgradient algorithm, soon later, for the incremental subgradient algorithm by Nedic and Bertsekas in [SIAM J. Optim., 2001, 12(1): 109‐138]. It was observed experimentally that the incremental approach has been very successful in solving large separable optimizations and that the dynamic step sizes generally have better computational performance than others in the literature. In the present paper, we propose two modified dynamic step size rules for the incremental subgradient algorithm and analyse the convergence and complexity properties of them. At last, the assignment problem is considered and the incremental subgradient algorithms employing different kinds of dynamic step sizes are applied to solve the problem. The computational experiments show that the two modified ones converges dramatically faster and more stable than the corresponding one in [SIAM J. Optim., 2001, 12(1): 109‐138]. Particularly, for solving large separable convex optimizations, we strongly recommend the second one (see Algorithm 3.3 in the paper) since it has interesting computational performance and is the simplest one. [ABSTRACT FROM AUTHOR]

Nowadays, the issue of traffic flow assignment has become an interdisciplinary topic that concerns multiple research areas and branches of science. This work is focussed on the mathematical and computational aspects of the equilibrium traffic assignment problem in the case when route flows are considered to be decision variables. Firstly, we obtain a fixed-point mapping with the explicit contraction operator, which is proven to equilibrate the journey times on feasible routes between a single origin-destination pair of nodes with the quadratic rate. Remarkable that from mathematical perspectives, the developed operator generalizes most path-equilibration operators already exploited by researchers. Secondly, we use the obtained fixed-point procedure to run the sequential path-equilibration algorithm for traffic flow assignment on well-known test urban road networks with arc-additive travel time functions. Our computational results appear to demonstrate higher accuracy of user-equilibrium traffic assignment solutions than the best ones known to us. In other words, developed within this paper sequential path-equilibration algorithm leads to solutions with less goal function values compared to the best solutions for today, according to our knowledge. [ABSTRACT FROM AUTHOR]

This paper presents a new way of selecting an initialisation for the k -modes algorithm that allows for a notion of game theoretic fairness that classic initialisations, namely those by Huang and Cao, do not. Our new method utilises the hospital-resident assignment problem to find the set of initial cluster centroids which we compare with two classical initialisation methods for k -modes: the original presented by Huang and the next most popular method of Cao and co-authors. To highlight the merits of our proposed method, two stages of analysis are presented. It is demonstrated that the proposed method is often able to offer computational speed-up of the order of 50 % . Improved clustering, in terms of a commonly used cost-function, was witnessed in several cases and can be of the order of 10 % , particularly for more complex datasets. [ABSTRACT FROM AUTHOR]

Smart security based on object detection is one of the important applications of edge computing in IoT. Anchors in object detection refer to points on the feature map, which can be used to generate anchor boxes and serve as training samples. Current object detection models do not consider the aspect ratio of the ground-truth boxes in anchor assignment and are not well-adapted to objects with very different shapes. Therefore, this paper proposes the Lightweight Anchor Dynamic Assignment algorithm (LADA) for object detection. LADA does not change the structure of the original detection model; first, it selects an equal proportional center region based on the aspect ratio of the ground-truth box, then calculates the combined loss of anchors, and finally divides the positive and negative samples more efficiently by dynamic loss threshold without additional models. The algorithm solves the problems of poor adaptability and difficulty in the selection of the best positive samples based on IoU assignment, and the sample assignment for eccentric objects and objects with different aspect ratios was more reasonable. Compared with existing sample assignment algorithms, the LADA algorithm outperforms the MS COCO dataset by 1.66% over the AP of the baseline FCOS, and 0.76% and 0.24% over the AP of the ATSS algorithm and the PAA algorithm, respectively, with the same model structure, which demonstrates the effectiveness of the LADA algorithm. [ABSTRACT FROM AUTHOR]

This research looks towards improving the accuracy and efficiency of orbit transfer speed increment estimation and task assignment for space patrol missions involving multiple platforms. First, we set up a quick prediction model for the increment in orbit transfer velocity. Then, a two-layered hybrid optimization framework is developed, with a deep neural network sub-model as the inner layer to find the optimal speed increase and the consensus-based bundle algorithm as the outer layer to solve the multi-task patrol sequence problem. Finally, the simulation and analysis of the patrol task assignment problem are conducted under two types of scenarios. The results show that the hierarchical optimization method proposed in this paper is three orders of magnitude faster than the traditional optimization method. In addition, the suggested hierarchical optimization method has significant promise in practical applications, where it can produce solutions more quickly to adapt to more complex patrol scenarios. • A multi-layered framework is established to handle the optimization of space patrol task assignment. • The deep neural network-based orbit-transfer speed increment calculator is proposed. • The consensus-based bundle algorithm-based task allocator achieves efficient assignments. • Calculating performance of the proposed method is evaluated. [ABSTRACT FROM AUTHOR]

In this paper, we study the D- and A-optimal assignment problems for regression models with experimental cost constraints. To solve these two problems, we propose two multiplicative algorithms for obtaining optimal designs and establishing extended D-optimal ( E D -optimal) and A-optimal ( E A -optimal) criteria. In addition, we give proof of the convergence of the E D -optimal algorithm and draw conjectures about some properties of the E A -optimal algorithm. Compared with the classical D- and A-optimal algorithms, the E D - and E A -optimal algorithms consider not only the accuracy of parameter estimation, but also the experimental cost constraint. The proposed methods work well in the digital example. [ABSTRACT FROM AUTHOR]

We formulate the Multi-Constrained Dynamic Traffic Assignment (DTA) problem as an instance of the nonlinear composite problem. To solve the problem, this paper introduces then the penalized nonlinear alternating direction method of multipliers (ADMM), a numerical algorithm that combines the nonlinear ADMM algorithm with the external penalty method. Numerical results are then presented, analyzed and compared against those obtained by applying the Reformulation-Linearization Technique (RLT)-based convex relaxation method together with piecewise linear approximation of the objective function. [ABSTRACT FROM AUTHOR]

Smart device networks form the backbone of many Internet of Things (IoT) applications. The performance of these systems depended on many factors. This includes their ability to connect to each other and network latency. In this paper, two algorithms are discussed that build a Peer-to-peer (P2P) overlay network. The focus is on real-time end-to-end remote instrumentation for IoT applications. P2P overlay networks are used for various purposes from content distribution through to media sharing. In contrast to traditional P2P systems, IoT systems can be highly sensitive to network latency and require low bandwidth. The main contributions of this paper are two algorithms to create overlay networks that assign peer nodes to super-peer nodes. The network contains a large number of smart devices and the key aim is to minimize system wide network latency. Other constraints regarding the nodes ability include the ability to become a super-peer node such as connectivity and limited processing capacities of the smart devices are also considered in context of a P2P remote instrumentation system. Both algorithms create a 3-hop network where the latency is lowered as much as possible with the given set of nodes. The algorithms have been validated through simulation. [ABSTRACT FROM AUTHOR]

• Investigate assigning shipping requests to crowdsourcees with time and capacity constraints • Propose a centralized, deep reinforcement learning-based approach • Present new state space representation encompassing spatial-temporal and capacity information • Embed heuristics-guided action choice in DRL to preserve tractability and enhance efficiency • Integrate rule-interposing into DRL to further enhance training and implementation efficiency This paper investigates the problem of assigning shipping requests to ad hoc couriers in the context of crowdsourced urban delivery. The shipping requests are spatially distributed each with a limited time window between the earliest time for pickup and latest time for delivery. The ad hoc couriers, termed crowdsourcees, also have limited time availability and carrying capacity. We propose a new deep reinforcement learning (DRL)-based approach to tackling this assignment problem. A deep Q network (DQN) algorithm is trained which entails two salient features of experience replay and target network that enhance the efficiency, convergence, and stability of DRL training. More importantly, this paper makes three methodological contributions: 1) presenting a comprehensive and novel characterization of crowdshipping system states that encompasses spatial-temporal and capacity information of crowdsourcees and requests; 2) embedding heuristics that leverage information offered by the state representation and are based on intuitive reasonings to guide specific actions to take, to preserve tractability and enhance efficiency of training; and 3) integrating rule-interposing to prevent repeated visiting of the same routes and node sequences during routing improvement, thereby further enhancing the training efficiency by accelerating learning. The computational complexities of the heuristics and the overall DQN training are investigated. The effectiveness of the proposed approach is demonstrated through extensive numerical analysis. The results show the benefits brought by the heuristics-guided action choice, rule-interposing, and having time-related information in the state space in DRL training, the near-optimality of the solutions obtained, and the superiority of the proposed approach over existing methods in terms of solution quality, computation time, and scalability. [ABSTRACT FROM AUTHOR]

In order to reduce the number and total distance of changing parking spaces in a parking lot or a given parking area through autonomous valet parking (AVP), in doing so to lower the related cost and the potential accident risk, this paper formula ted a vehicle-slot matching optimization model which satisfied the shared parking requirement. In view of the feature of autonomous vehicle freely translocating during parking, this paper defined the match, match slice and match map corresponding to decision variable and feasible solution by subdividing the shared parking demand and supply in time. By conception replacement, the paper changed the searching effective neighbor of match map into the classic assignment problem and solved it with Hungarian algorithm. In view of the NP-hard feature of the matching model, this paper proposed a designed tabu searching algorithm. Numerical analysis not only verified the rationality of this model and the effectiveness of the algorithm, also proved that the model and algorithm could deal with the shared parking of conventional vehicles. The results show that AVP can improve the utility of shared parking berths and increase the number of served vehicles. [ABSTRACT FROM AUTHOR]

An incidence of a graph G is a vertex-edge pair (v , e) such that the vertex v is incident with the edge e. A proper incidence k-coloring of a graph is a coloring of its incidences involving k colors so that two incidences (u , e) and (w , f) receive distinct colors if and only if u = w , or e = f , or u w ∈ { e , f }. In this paper, we present some idea of using the incidence coloring to model a kind of multi-frequency assignment problem , in which each transceiver can be simultaneously in both sending and receiving modes, and then establish some theoretical and algorithmic aspects of the incidence coloring. Specifically, we conjecture that if G is the Mycielskian of some graph then it has a proper incidence (Δ (G) + 2) -coloring. Actually, our conjecture is motivated by the " (Δ + 2) conjecture" of Brualdi and Quinn Massey in 1993, which states that every graph G has a proper incidence (Δ (G) + 2) -coloring, and was disproved in 1997 by Guiduli, who pointed out that the Paley graphs with large maximum degree are counterexamples (yet they are all known counterexamples to the " (Δ + 2) conjecture", and are not Mycielskians of any graph). To support our conjecture, we prove in this paper that if G is the Mycielskian of a graph H with | H | ≥ 3 Δ (H) + 2 , then we can construct a proper incidence (Δ (G) + 1) -coloring of G in cubic time, and if G is the Mycielskian of an incidence (Δ (H) + 1) -colorable graph H with | H | ≤ 2 Δ (H) , or the Mycielskian of an incidence (Δ (H) + 2) -colorable graph H with | H | ≥ 2 Δ (H) + 1 , then G has a proper incidence (Δ (G) + 2) -coloring. The minimum positive integer k such that the Mycielskian of a cycle or a path has a proper incidence k -coloring is also determined. [ABSTRACT FROM AUTHOR]

In this paper, we study the quadratic assignment problem with a rank-one cost matrix (QAP-R1). Four integer-programming formulations are introduced of which three are assumed to have partial integer data. Unlike the standard quadratic assignment problem, some of our formulations can solve reasonably large instances of QAP-R1 with impressive running times and are faster than some metaheuristics. Pairwise relative strength of the LP relaxations of these formulations are also analyzed from theoretical and experimental points of view. Finally, we present a new metaheuristic algorithm to solve QAP-R1 along with its computational analysis. Our study offers the first systematic experimental analysis of integer-programming models and heuristics for QAP-R1. The benchmark instances with various characteristics generated for our study are made available to the public for future research work. Some new polynomially solvable special cases are also introduced. Summary of Contribution: This paper aims to advance our knowledge and ability in solving an important special case of the quadratic assignment problem. It shows how to exploit inherent properties of an optimization problem to achieve computational advantages, a strategy that was followed by researchers in model building and algorithm developments for decades. Our computational results attest to this time-tested general philosophy. The paper presents the first systematic computational study of the rank one quadratic assignment problem, along with new mathematical programming models and complexity analysis. We believe the theoretical and computational results of this paper will inspire further research on the topic and will be of significant value to practitioners using rank one quadratic assignment models. [ABSTRACT FROM AUTHOR]

This paper proposes a quantum-inspired evolutionary algorithm (QiEA) to solve an optimal service-matching task-assignment problem. Our proposed algorithm comes with the advantage of generating always feasible population individuals and, thus, eliminating the necessity for a repair step. That is, with respect to other quantum-inspired evolutionary algorithms, our proposed QiEA algorithm presents a new way of collapsing the quantum state that integrates the problem constraints in order to avoid later adjusting operations of the system to make it feasible. This results in lower computations and also faster convergence. We compare our proposed QiEA algorithm with three commonly used benchmark methods: the greedy algorithm, Hungarian method and Simplex, in five different case studies. The results show that the quantum approach presents better scalability and interesting properties that can be used in a wider class of assignment problems where the matching is not perfect. [ABSTRACT FROM AUTHOR]

Achieving accurate and real-time perception of environmental targets in complex traffic scenes based on visual sensors is a challenging research problem in the field of autonomous driving technology. In methods to date, it is difficult to effectively balance the detection accuracy and speed. To this end, this paper proposes an interactive and lightweight visual detection algorithm – YRDM (Your Region Decision-Making) – based on the concepts of efficient mining and utilisation of target feature information, lightweight network structure, and optimisation of label allocation for highly practical detection of ambient targets in autonomous driving scenarios. First, a two-stage algorithm architecture consisting of four low-parameter subnetworks is constructed with the goal of efficiently mining and utilising target feature information, and the accuracy and effectiveness of the algorithm are balanced through the interaction of information between the subnetworks. Second, in order to further improve the detection speed, lightweight convolution is introduced into the structure of the YRDM network to construct the DSC3 module, which allows lightweight processing of the subnetwork structure. Finally, by converting the label assignment problem into an optimal transport problem, adaptation to the global nature of the samples by YRDM is improved, allowing better detection accuracy. The algorithm is tested with two major public datasets, BDD100K and KITTI, and a large number of experimental results show that the comprehensive performance of YRDM is better than other existing algorithms. In addition, ablation experiments and mobile terminal device deployment experiments further demonstrate the effectiveness and real-time performance of this algorithm. • Proposed a two-stage detection algorithm called your region decision-making (YRDM). • YRDM addressed challenges of complex traffic and limited computing resources. • YRDM achieved 57.8 % accuracy (BDD100K); 89.6 % (KITTI) with 2.98 GFLOPs. • Info interaction in low-parameter subnets boosts accuracy. • Lightweight convolution and DSC3 enhanced speed and efficiency. [ABSTRACT FROM AUTHOR]

Airport runway assignment and gate assignment are both crucial problems for large multirunway airports. A cooperative schedule for the runway and gate can have a significant effect on airport ground operation efficiency and safety. This paper focuses on the joint assignment problem of runways and gates considering parking time differences and airline preferences. A quadratic model is established to reduce taxiing fuel consumption loss and increase the robustness of gate assignment. An improved branch-and-price algorithm is proposed by utilizing an improved pulse algorithm and various acceleration strategies to improve the solution performance. The actual flight data at an international hub airport are utilized to validate the proposed model. The results indicate that the joint assignment model can effectively reduce ground taxiing loss, optimize gate assignment robustness, and increase the utilization rate of contact gates. The proposed algorithm also achieves better computational accuracy and efficiency. • Proposed joint runway–gate assignment model can reduce the taxiing loss and gate robustness loss. • The model optimizes the taxiing and gate robustness while ensuring airline's preference. • A better solution is obtained by an improved branch-and-price method. • Experiments are designed to verify the value of the joint model. [ABSTRACT FROM AUTHOR]

Strategy-based equilibrium traffic assignment (SETA) problems define travel choice broadly as a strategy rather than a simple path. Travelers navigating through a network based on a strategy end up following a hyperpath. SETA is well suited to represent a rich set of travel choices that take place en route at nodes, such as transit passengers' transfer decisions, truckers' bidding decisions, and taxi drivers' reposition decisions. This paper recognizes and highlights the commonalities among classical and emerging SETA problems and proposes to unify them within the same modeling framework, built on the concept of a hypergraph. A generic hyperbush algorithm (HBA) is developed by decomposing a hypergraph into destination-based hyperbushes. By constructing hyperbushes and limiting traffic assignments to them, HBA promises to obtain more precise solutions to larger instances of SETA problems at a lower computational cost, both in terms of CPU time and memory consumption. To demonstrate its generality and efficiency, we tailor HBA to solve two SETA problems. The results confirm that HBA consistently outperforms the benchmark algorithms in the literature, including two state-of-the-art hyperpath-based algorithms. To obtain high-quality equilibrium solutions for SETA instances of practical size, HBA runs up to five times faster than the best competitor with a fraction of its memory consumption. [ABSTRACT FROM AUTHOR]

In intelligent warehouse, the problem of transporting goods in intelligent warehouse is becoming increasingly complex, and the traditional way of automatically guiding vehicles (AGVs) is inefficient, so automated robot systems are introduced into intelligent warehouses. In this paper, a task assignment model for robots is presented with the transportation problem of robots in intelligent warehouse as the research background. To solve the robot task assignment problem in intelligent warehouse, a novel Pareto-based multiobjective optimization algorithm (MOEA) is proposed, and the aggregation function is invoked to replace the crowding distance; the brain storm operator is used for crossover and mutation. Finally, the ability of the algorithm to solve the benchmark test problem suite and real-world problems is experimentally confirmed. [ABSTRACT FROM AUTHOR]

The weapon target assignment (WTA) problem is an important task to tactical arrangements in military commitment operations. It describes the optimal method to allocate defense in opposition to threats in fighting situations. It is an NP-complete issue in which no accurate outcome for all conceivable situations is known. The time performance of created algorithms is a major challenge in modeling the WTA problem, which has only been lately considered in related papers. This article improves the recently developed algorithm called improved Tunicate Swarm Algorithm (iTSA) which is inspired by the natural behavior of tunicates to solve the WTA problem. The suggested method is compared with well-known metaheuristic approaches. The experimental findings show that the method presented works better than previous competing metaheuristic approaches. [ABSTRACT FROM AUTHOR]

The Weapon-Target Assignment (WTA) problem aims to assign a set of weapons to a number of assets (targets), such that the expected value of survived targets is minimized. The WTA problem is a nonlinear combinatorial optimization problem known to be NP-hard. This paper applies several existing techniques to linearize the WTA problem. One linearization technique (Camm et al. in Oper Res 50(6):946–955, 2002) approximates the nonlinear terms of the WTA problem via convex piecewise linear functions and provides heuristic solutions to the WTA problem. Such approximation problems are, though, relatively easy to solve from the computational point of view even for large-scale problem instances. Another approach proposed by O'Hanley et al. (Eur J Oper Res 230(1):63–75, 2013) linearizes the WTA problem exactly at the expense of incorporating a significant number of additional variables and constraints, which makes many large-scale problem instances intractable. Motivated by the results of computational experiments with these existing solution approaches, a specialized new exact solution approach is developed, which is called branch-and-adjust. The proposed solution approach involves the compact piecewise linear convex under-approximation of the WTA objective function and solves the WTA problem exactly. The algorithm builds on top of any existing branch-and-cut or branch-and-bound algorithm and can be implemented using the tools provided by state-of-the-art mixed integer linear programming solvers. Numerical experiments demonstrate that the proposed specialized algorithm is capable of handling very large scale problem instances with up to 1500 weapons and 1000 targets, obtaining solutions with optimality gaps of up to 2.0 % within 2 h of computational runtime. [ABSTRACT FROM AUTHOR]

The objective of this paper is to search the efficient arrangements of huge multi-objective assignment problem (MOAP). Here, we have modified the Jaya algorithm with the help of product operator in exponential membership functions for solving MOAP. We have also provided one numerical illustration from the real world for verifying the results of proposed approach. At last, the results of the proposed approach are contrasted with reputed approaches and from that we can conclude that the proposed approach is better for solving the MOAP. [ABSTRACT FROM AUTHOR]

In order to minimize the average completion time of a series of geo-distributed data analytical jobs, this paper first introduced online random scheduling algorithm ranT A. ranT A actually showed the preference on the task assignment under the consideration of both computing capacity of edges and the network bandwidth. Furthermore, in order to avoid overloading those edges with low computing capacities, this paper proposed data redistribution mechanism ranT A-data based on ranT A by redistributing some data to the central data center along with the tasks. The result of ranT A -data could be proved concentrated on its optimum with high probability. Extensive simulations show that ranTA-data improves nearly 30% performance compared with traditional algorithms. [ABSTRACT FROM AUTHOR]

This paper integrates, from a tactical perspective, berth allocation and quay-crane assignment, two important, closely related decisions in container terminal operations in a single model. To obtain optimal solutions, a branch-and-price algorithm is sought in this paper under the framework of Dantzig–Wolfe decomposition. The algorithm decomposes the original problem to a master problem that links all vessels competing for the shared resources of berths and quay cranes and multiple per-vessel pricing subproblems that can be solved efficiently in polynomial time. Specifically, in the stage of generating promising initial feasible columns, three heuristics are adopted; during the column-updating stage, the subgradient-based Lagrangian relaxation is introduced to tackle the possibly encountered degeneracy phenomenon; the branching strategy is implemented in the pricing subproblem rather than in the master problem as reported in the literature with the benefit of avoiding incurring new dual prices, simplifying the branching process; and both breadth- and depth-first searching policies are tested to select the next node to explore. With real-life data, extensive numerical experiments are conducted to select the best choice for each stage with the strengths and drawbacks of each choice provided. And then the superiority of the branch-and-price algorithm configured with the selected combination of strategies is verified by comparing it with both CPLEX, a general-purpose solver, and a set-partitioning model, a dedicated algorithm reported in the literature. In addition, the decomposition by vessels adopted in this paper is also verified numerically by comparing it with the decomposition by berths reported in the literature, and the performance of the algorithm for other problem settings has also been tested. In conclusion, the numerical experiments show that our method outperforms the commercial solver and state-of-the-art solution methods reported in the literature in terms of both solution quality and computational time. [ABSTRACT FROM AUTHOR]

• Based on the model decomposition approach, two new parallel algorithmic frameworks are proposed. • The parallel algorithm B-ADMM is developed by employing the concept of bush. • Integrating the parallel block coordinate descent (PBCD) method and the B-ADMM algorithm, then a bi-level parallel algorithm PBCD-ADMM is developed. • To validate the two algorithms proposed with much large-scale networks. This paper introduces two novel parallel algorithmic frameworks to address the user equilibrium traffic assignment problem (UE-TAP). Most of the existing solution algorithms for the UE-TAP are executed in a sequential manner. This study endeavors to explore parallel computing methods based on model decomposition. Considering that the TAPs can be decomposed based on their origins, thus, following the spirit of the alternating direction method of multipliers (ADMM), a new parallel algorithm B-ADMM is proposed, which integrates the concept of the bush. Subsequently, the convergence of the proposed algorithm is rigorously proven. To enhance the algorithmic parallelism while maintaining the convergence efficiency of the B-ADMM algorithm, this paper further employs the parallel block coordinate descent (PBCD) method to improve the B-ADMM algorithm. We develop a bi-level parallel algorithm PBCD-ADMM, in which the independent origins/bushes are separated into several blocks, and the origin/bush-based restricted subproblems in each block can be solved in parallel. Furthermore, for the given bush belonging to a block, the bush links can also be grouped into several sub-blocks based on the original link-blocking scheme. Thus, these link-based subproblems in each sub-block can also be solved in parallel. A numerical experiment is conducted to validate the proposed algorithms, which indicates that the two new parallel algorithms perform better in terms of convergence speed compared with the original ADMM algorithm. [ABSTRACT FROM AUTHOR]

The Exact Satisfiability problem asks if we can find a satisfying assignment to each clause such that exactly one literal in each clause is assigned 1, while the rest are all assigned 0. We can generalise this problem further by defining that a C j clause is solved iff exactly j of the literals in the clause are 1 and all others are 0. We now introduce the family of Generalised Exact Satisfiability problems called G i XSAT as the problem to check whether a given instance consisting of C j clauses with j ∈ { 0 , 1 , ... , i } for each clause has a satisfying assignment. In this paper, we present faster exact polynomial space algorithms, using a nonstandard measure, to solve G i XSAT, for i ∈ { 2 , 3 , 4 } , in O (1.3674 n) time, O (1.5687 n) time and O (1.6545 n) time, respectively, using polynomial space, where n is the number of variables. This improves the current state of the art for polynomial space algorithms from O (1.4203 n) time for G2XSAT by Zhou, Jiang and Yin and from O (1.6202 n) time for G3XSAT by Dahllöf and from O (1.6844 n) time for G4XSAT which was by Dahllöf as well. In addition, we present faster exact algorithms solving G2XSAT, G3XSAT and G4XSAT in O (1.3188 n) time, O (1.3407 n) time and O (1.3536 n) time respectively at the expense of using exponential space. [ABSTRACT FROM AUTHOR]

This paper presents a new approach to accurately and efficiently identifying a large number of wireless devices blindly installed to known three-dimensional installation/fitting points, based on received signal strengths (RSSs) between the devices. The approach is non-trivial because of the factorial, mapping nature of the considered problem, the multiplicative ranging errors of the RSS measurements (with standard deviation of 5–7 dB), and the requirement of high mapping accuracy in many internet-of-things (IoT) applications, e.g., industrial IoT and aircraft. The consideration of a structured environment where the set of candidate node positions is known beforehand shifts the problem of interest from a pure position estimation problem to a position assignment problem. The key idea of the proposed approach is that we interpret the position mapping problem with a probabilistic graphical model, where the factorial nature of mapping (more specifically, the mutual exclusiveness of devices at every installation point) is fully captured. A max-product belief propagation is designed against the probabilistic graph, to estimate the max-marginal position distribution of each device. The Kuhn-Munkres algorithm is applied to preserve the mutual exclusiveness of devices throughout the belief propagation and to decide device locations based on the estimated position distributions. Large-scale simulations and field tests are carried out, showing that the new approach achieves close-to-100% accuracy in simulations with hundreds of blindfolded devices under RSS measurement errors with standard deviation of 5–7 dB. Our approach also achieves 100% accuracy in all field trials with 76 devices inside the cabin of a Fokker 100 airplane, dramatically outperforming baseline techniques. [ABSTRACT FROM AUTHOR]

With the explosive growth in the scale of cloud computing infrastructures, reliability and energy efficiency have become important concerns considering the great complexity of cloud data centers. There is an urgent need for efficient task assignment that can dispatch tasks to appropriate cloud data center servers, which is critical to achieve reliability and energy efficiency in current cloud data centers. Most of the research on task assignment focuses on only one of the objectives of reliability and energy efficiency, while the two objectives are intrinsically conflicting with each other. In this paper, we deal with the problem of task assignment in data centers, with the objective of minimizing the energy consumption while providing failure tolerance to task execution failure. We propose a reliability-aware and energy-efficient task replica assignment algorithm based on running task replicas at a low speed and enabling multiple task replicas to share the same server resources. Each task in a job processed by the cloud computing platform has two instances: main task and task replica (shadow). Each main task runs on an individual server, and the task replica associated with the main task is assigned on a different server. The main tasks run at the full server speed, while the task replicas run at a lower rate than the main tasks. The task replicas can be mapped onto dedicated backup servers or be assigned to the servers on which the main tasks are running. Multiple task replicas can share the same server resources to reduce the number of servers required. We conduct experiments through simulations. Experimental results demonstrate that the proposed algorithm can effectively reduce the energy consumption, while achieving a good balance between the number of servers used and job completion time. [ABSTRACT FROM AUTHOR]

• Propose the concepts of line strategy (LS) and node strategy (NS) and a novel methodology adopting the decision variables of LS and NS proportions. • Impose transfer constraints explicitly and mix all the passengers with the same maximal number of transfers together. • Establish the LNS (line and node strategy) -based model on the original transit networks and reduce the scope of the feasible transfer nodes by the maximal transfer constraints. • Adopt both the method of successive averages (MSA) and a projection algorithm to solve the LNS-based model. • The performance of the LNS-based model and algorithm on a transit subnetwork of Beijing showcases its huge advantage. Passengers traveling on transit networks involve two kinds of decision-making strategies: deciding which lines are attractive at an origin or transfer node (denoted line strategy, LS), or deciding which node to transfer at when riding a line (denoted node strategy, NS). Combining these two strategies, this paper proposes a novel variational inequality formulation for the user equilibrium passenger assignment problem. The inclusion of the NS eliminates the need for passenger assignment on a large augmented graph, reducing the modeling complexity and making it easier to track all passengers' travel routes. Moreover, constraints on the maximal number of transfers—which are crucial in practical decision-making on transit networks—are explicitly included, further drastically reducing the set of passengers' feasible strategies. Furthermore, some extant strategy-based transit assignment models are shown to be a special case of the proposed model when the transfer constraint is removed. Finally, the properties of the proposed model are illustrated on a small network, and the model and algorithm exhibit huge advantages on the chosen transit subnetwork of Beijing. [ABSTRACT FROM AUTHOR]

For the large-scale search and rescue (S&R) scenarios, the centralized and distributed multi-UAV multitask assignment algorithms for multi-UAV systems have the problems of heavy computational load and massive communication burden, which make it hard to guarantee the effectiveness and convergence speed of their task assignment results. To address this issue, this paper proposes a hierarchical task assignment strategy. Firstly, a model decoupling algorithm based on density clustering and negotiation mechanism is raised to decompose the large-scale task assignment problem into several nonintersection and complete small-scale task assignment problems, which effectively reduces the required computational amount and communication cost. Then, a cluster head selection method based on multiattribute decision is put forward to select the cluster head for each UAV team. These cluster heads will communicate with the central control station about the latest assignment information to guarantee the completion of S&R mission. At last, considering that a few targets cannot be effectively allocated due to UAVs' limited and unbalanced resources, an auction-based task sharing scheme among UAV teams is presented to guarantee the mission coverage of the multi-UAV system. Simulation results and analyses comprehensively verify the feasibility and effectiveness of the proposed hierarchical task assignment strategy in large-scale S&R scenarios with dispersed clustering targets. [ABSTRACT FROM AUTHOR]

We prove a general result demonstrating the power of Lagrangian relaxation in solving constrained maximization problems with arbitrary objective functions. This yields a unified approach for solving a wide class of subset selection problems with linear constraints. Given a problem in this class and some small ε ∈ (0 , 1) , we show that if there exists an r -approximation algorithm for the Lagrangian relaxation of the problem, for some r ∈ (0 , 1) , then our technique achieves a ratio of r r + 1 − ε to the optimal, and this ratio is tight. Using the technique we obtain (re)approximation algorithms for natural (reoptimization) variants of classic subset selection problems, including real-time scheduling, the maximum generalized assignment problem (GAP) and maximum weight independent set. For all of the problems studied in this paper, the number of calls to the r -approximation algorithm, used by our algorithms, is linear in the input size and in log (1 ∕ ε) for inputs with a cardinality constraint, and polynomial in the input size and in log (1 ∕ ε) for inputs with an arbitrary linear constraint. [ABSTRACT FROM AUTHOR]

• We re-analyze the algorithm presented by Bhore et al., and prove a time bound of 2 O (κ 2) ⋅ | V | improving the previous bound of κ O (κ 2) ⋅ | V |. • We show that fixed-order book thickness parameterized by the pathwidth of the vertex ordering does not admit a polynomial kernel unless NP ⊆ coNP/poly. • We also show that a generalized version of fixed-order book thickness admits a parameterized algorithm running in time (c + 2) O (κ 2) ⋅ | V |. Given a graph G = (V , E) with a vertex ordering ≺, the fixed-order book thickness problem asks whether there is a page assignment σ such that 〈 ≺ , σ 〉 is a k -page book embedding of G. This problem is NP-complete even for any fixed k greater than 3. Recently, Bhore et al. (2019, 2020) [1,2] presented a parameterized algorithm with respect to the pathwidth κ of the vertex ordering. In this paper, we first re-analyze the running time for Bhore et al.'s algorithm, and prove a bound of 2 O (κ 2) ⋅ | V | improving Bhore et al.'s bound of κ O (κ 2) ⋅ | V |. Then, we show that fixed-order book thickness parameterized by the pathwidth of the vertex ordering does not admit a polynomial kernel unless NP ⊆ coNP/poly. Finally, we show that a generalized fixed-order book thickness problem, in which a budget of at most c crossings over all pages was given, admits a parameterized algorithm running in time (c + 2) O (κ 2) ⋅ | V |. [ABSTRACT FROM AUTHOR]

Highlights • In this paper a Redundancy Allocation problem (RAP) for a queueing system is modeled. • Optimal number of repairmen and redundant servers are found by which queueing and maintenance costs are minimized. • Four random search algorithms are developed to deal with different structures of solution space. • Two algorithms for unimodal objective functions and two algorithms for multimodal objective functions are developed. Abstract The Redundancy Allocation Problem (RAP) is becoming all the time more important in system reliability design. Therefore, RAP has been studied vastly for different systems and under various assumptions. One of the important systems that RAP can be applied to them is queuing systems. In many applications, reliability of queuing systems need to be improved with regard to some queuing and reliability cost constraints. Despite the importance of queuing systems in real world situations, RAP of these systems have not gained attention in the literature. Therefore, RAP of a queuing system with maintenance considerations and including queueing costs in the modeling of RAP is considered in this paper. To find optimal solutions of the problem, four random search algorithms are developed and compared based on the problem structures. According to the experiments, for unimodal solution spaces algorithms 1 and 2 and for multimodal solution spaces algorithms 3 and 4 are recommended. [ABSTRACT FROM AUTHOR]

In the practical situation, the QC setup time cannot be negligible in the decision making process due to the QC speed limitations of shifting along the quay. This paper established the deterministic model of the berth allocation and quay crane assignment problem considered the QC setup time of shifting along the quay. This paper proposed the artificial fish swarm algorithm (AFSA) with the heuristic adjusted strategies to optimize the priority list of vessels served and allocate the QC numbers. The experiment results show the improved AFSA algorithm has more efficiency and competitive quality of solution than the CPLEX. [ABSTRACT FROM AUTHOR]

We revisit the maximum satisfiability problem (Max-SAT) in the data stream model. In this problem, the stream consists of m clauses that are disjunctions of literals drawn from n Boolean variables. The objective is to find an assignment to the variables that maximizes the number of satisfied clauses. Chou et al. (FOCS 2020) showed that Ω (n) space is necessary to yield a 2 / 2 + ε approximation of the optimum value; they also presented an algorithm that yields a 2 / 2 − ε approximation of the optimum value using O (ε − 2 log ⁡ n) space. In this paper, we not only focus on approximating the optimum value, but also on obtaining the corresponding Boolean assignment using sublinear o (m n) space. We present randomized single-pass algorithms that w.h.p.1 yield: • A 1 − ε approximation using O ˜ (n / ε 3) space and exponential post-processing time • A 3 / 4 − ε approximation using O ˜ (n / ε) space and polynomial post-processing time. Our ideas also extend to dynamic streams. However, we show that the streaming k -SAT problem, which asks whether one can satisfy all size- k input clauses, must use Ω (n k) space. We also consider the related minimum satisfiability problem (Min-SAT), introduced by Kohli et al. (SIAM J. Discrete Math. 1994), that asks to find an assignment that minimizes the number of satisfied clauses. For this problem, we give a O ˜ (n 2 / ε 2) space algorithm, which is sublinear when m = ω (n) , that yields an α + ε approximation where α is the approximation guarantee of the offline algorithm. If each variable appears in at most f clauses, we show that a 2 f n approximation using O ˜ (n) space is possible. Finally, for the Max-AND-SAT problem where clauses are conjunctions of literals, we show that any single-pass algorithm that approximates the optimal value up to a factor better than 1/2 with success probability at least 2/3 must use Ω (m n) space. [ABSTRACT FROM AUTHOR]

Gate assignment problem (GAP) is the core issue of airport operation management. However, the limited resources of airport gates and the increase of flight scale result in serious problems for gate allocation. In this paper, to provide decision-making support for large-scale GAPs, a model based on gate assignment rules (e.g., flight type constraints, safe time interval constraints, and adjacency conflict constraints) is built to formulate the problem. An improved adaptive parallel genetic algorithm (APGA) is then designed to solve the model. The algorithm is effective because it introduces the idea of elite strategy and parallel design and can adaptively adjust the crossover probability. Moreover, different instances are presented to demonstrate the proposed algorithm. The calculation results of this algorithm are compared with those of standard genetic algorithm and CPLEX, which show that the proposed algorithm has better performance and takes a shorter computational time. In addition, we verify the stability and practicability of the algorithm by repeated experiments on large-scale flight data. [ABSTRACT FROM AUTHOR]

An airport gate is the core resource of an airport operation, which is an important place for passengers to get on and off the aircraft and for maintaining aircraft. It is the prerequisite for other related dispatch. Effective and reasonable allocation of gates can reduce airport operating costs and increase passenger satisfaction. Therefore, an airport gate assignment problem (AGAP) needs to be urgently solved in the actual operation of the airport. In this paper, considering the actual operation of the airport, we formulate an integer programming model for AGAP by considering multiple constraints. The model aims to maximize the number of passengers on flights parked at the gate. A tabu search-based algorithm is designed to solve the problem. In the process of algorithm design, an effective initial solution is obtained. A unique neighborhood structure and search strategy for tabu search are designed. The algorithm can adapt to the dynamic scheduling of airports. Finally, tests are performed using actual airport data selected from Kunming Changshui International Airport in China. The experimental results indicate that the proposed method can enhance the local search ability and global search ability and get satisfactory results in a limited time. These results provide an effective support for the actual gate assignment in airport operations. [ABSTRACT FROM AUTHOR]

In this paper, we study the handover (HO), and power allocation problem in a two-tier heterogeneous network (HetNet), which consists of a macro base station, and some millimeter-wave (mmWave) small base stations. We establish an HO management, and power allocation scheme to maximize the overall throughput while reducing the HO frequency. In particular, considering the interrelationship among decisions made by different user equipments (UEs), we first model the HO, and power allocation problem as a fully cooperative multi-agent task, in which all agents, i.e., UEs, have the same target. Then, to solve the multi-agent task, and get decentralized policies for each UE, we develop a multi-agent reinforcement learning (MARL) algorithm based on the proximal policy optimization (PPO) method, by introducing the centralized training with decentralized execution framework. That is, we use global information to train policies for each UE, and after the training is finished, each UE obtains a decentralized policy, which can be implemented only based on each UE's local observation. Specially, we introduce the counterfactual baseline to address the credit assignment problem in centralized learning. Due to the centralized training, the decentralized polices learned by multi-agent PPO (MAPPO) can work more cooperatively. Finally, the simulation results demonstrate that our method can achieve better performance comparing with other existing works. [ABSTRACT FROM AUTHOR]

• NP-hardness proof for the partial assignment problem. • A 1 / m -approximation for the partial assignment problem with general value functions. • A (1 − 1 / e) -approximation for the partial assignment problem with sub- modular value functions. In the partial assignment problem, a seller has an item set M = { i 1 , i 2 , ... , i m } , the amount of each item is exactly one. There are n buyers N = { b 1 , b 2 ,... , b n } , each buyer b p has a preferred bundle B p ⊆ M and a value function f p (⋅). Assume that each item should be sold integrally and thus can be only assigned to at most one buyer. In previous works, buyers are often considered to be single-minded, i.e., a buyer can be either assigned the whole preferred bundle, or nothing. In this paper, we consider a more generalized and realistic model where the buyer can be partially satisfied, i.e., buyer b p can have some positive value if the seller assigns a subset of b p 's preferred bundle. However, there might be exponential number of subsets, to tackle this situation, a value oracle is implemented. We can get the value f p (S p) for buyer b p and S p ⊆ B p by querying the value oracle. The objective is to assign items to buyers such that the total values are maximized, i.e., max ⁡ ∑ p = 1 n f p (S p). We first show that in this model, maximizing the total values is NP-hard. We then propose provably efficient approximation algorithms for general and submodular value functions respectively. If the value function satisfies non-negative, monotone and normalized, an 1 / m -approximation algorithm can be achieved. If the value function is submodular, the total values can be approximated within a factor of (1 − 1 / e). [ABSTRACT FROM AUTHOR]

Introduction of Neutrosophic sets and Neutrosophic numbers paves a way to handle uncertainty more effectively. In this paper we propose a new approach for ranking neutrosophic number by using its magnitude. We develop an algorithm for the solution of neutrosophic assignment problems involving pentagonal neutrosophic number. The proposed method is easy to understand and to apply for finding solution of neutrosophic assignment problems occurring in real life situations. To show the proposed strategy numerical models are given and the acquired results are analyzed. [ABSTRACT FROM AUTHOR]

Resources allocation (RA) is a challenging task in many fields and applications including communications and computer networks. The conventional solutions of such problems usually come with a time and memory cost, especially for massive networks such as Internet-of-Things (IoT) networks. In this paper, two RA deep network models are proposed for enabling a clustered underlay IoT deployment, where a group of IoT nodes are uploading information to a centralized gateway in their vicinity by reusing the communication channels of conventional cellular users. The RA problem is formulated as a two-dimensional matching problem, which can be expressed as a traditional linear sum assignment problem (LSAP). The two proposed models are based on the recurrent neural network (RNN). Specifically, we investigate the performance of two long short-term memory (LSTM) based architectures. The results show that the proposed techniques could be used as replacement of the well-known Hungarian algorithm for solving LSAPs due to its ability to find the solution for the problems with different sizes, high accuracy, and very fast execution time. Additionally, the results show that the obtained accuracy outperforms the state-of-the-art deep network techniques. [ABSTRACT FROM AUTHOR]

A robotic mobile fulfillment system (RMFS) performs the order fulfillment process by bringing inventory to workers at pick-pack-and-ship warehouses. In the RMFS, robots lift and carry shelving units, called inventory pods, from storage locations to picking stations where workers pick items off the pods and put them into shipping cartons. The robots then return the pods to the storage area and transport other pods. In this article, we consider an item assignment problem in the RMFS in order to maximize the sum of similarity values of items in each pod. We especially focus on a reoptimization heuristic to address the situation where the similarity values are altered so that a good assignment solution can be obtained quickly with the changed similarity values. A constructive heuristic algorithm for the item assignment problem is developed, and then, a reoptimization heuristic is proposed based on the constructive heuristic algorithm. Then, computational results for several instances of the problem with 10–500 items are presented. We further analyze the case for which an item type can be placed into two pods. Note to Practitioners—This article proposes an efficient heuristic algorithm for assigning items to pods in a robotic mobile fulfillment system (RMFS) so that items ordered together frequently are put into the same pod. Computational results with 10–500 items show that the gaps from upper bounds are very small on average. For cases where the similarity values between items change or their estimation is not accurate due to the fluctuations in demand, a reoptimization heuristic algorithm that alters the original assignment is developed. The experimental results show that the reoptimization algorithm is robust when perturbation levels are approximately 40%–50% of the original similarity values with much less computation times. We believe that this research work can be very helpful for operating the RMFS efficiently. [ABSTRACT FROM AUTHOR]

State assignment is the most critical step in the synthesis and optimization of sequential circuits as it significantly impacts sequential circuits area and power. Due to the high complexity of the state assignment problem and the ineffectiveness of existing deterministic algorithms in generating good solutions, evolutionary algorithms can be employed to obtain more effective state assignment solutions. In this paper, we propose a probabilistic tabu search (PTS) state assignment algorithm that is employed for the optimization of area and power of sequential circuits. The proposed algorithm is based on tabu search with the addition of exploiting code swap probabilities to prune the search space more effectively. Code swap probabilities are updated dynamically during the execution of the algorithm in such a way that code swaps that result in relatively inferior solutions will be assigned lower probabilities while those that result in good solutions will be assigned higher probabilities. In addition, tabu list size is changed dynamically during execution to help the algorithm get out of local minima. Based on experimental results, we show that the proposed PTS state assignment algorithm is more effective than all existing state assignment algorithms as it generates state assignment solutions with significantly lower area and power. [ABSTRACT FROM AUTHOR]

This paper considers a single-machine due-window assignment scheduling problem with position-dependent weights, where the weights only depend on their position in a sequence. The objective is to minimise the total weighted penalty of earliness, tardiness, due-window starting time, and due-window size of all jobs. Optimal properties of the problem are given, and then, a polynomial-time algorithm is provided to solve the problem. An extension to the problem is offered by assuming general position-dependent processing time. [ABSTRACT FROM AUTHOR]

The Weapon-Target Assignment (WTA) problem is one of the most important optimization problems in military operation research. In the WTA problem, assets of defense aim the best assignment of each weapon to target for decreasing expected damage directed by the offense. In this paper, Modified Crow Search Algorithm (MCSA) is proposed to solve the WTA problem. In MCSA, a trial mechanism is used to improve the quality of solutions using parameter LIMIT. If the solution is not improved after a predetermined number of iterations, then MCSA starts with a new position in the search space. Experimental results on the different sizes of the WTA problem instances show that MCSA outperforms CSA in all problem instances. Also, MCSA achieved better results for 11 out of 12 problem instances compared with four state-of-the-art algorithms. The source codes of MCSA for the WTA are publicly available at http://www.3mrullah.com/MCSA.html. [ABSTRACT FROM AUTHOR]

The application of network slicing to mobile edge computing (MEC) systems has aroused great interests from both academia and industry. However, the optimization of network slicing and MEC in most existing research works only focuses on resource slicing, energy scheduling, and power allocation from the perspective of mobile devices, without considering the operator's revenue. In this paper, we propose a novel framework for network slicing in MEC systems, including slice request admission and a revenue model, to investigate the operator's revenue escalation problem while considering traffic variations. The revenue model is mainly composed of the longer-term revenue and short-term revenue. Particularly, we jointly optimize slice request admission in the long-term and resource allocation in the short-term to maximize the operator's average revenue. By employing the Lyapunov optimization technique, we develop an algorithm without requiring any prior-knowledge of traffic distributions, referred to as the DNSRA, to solve the problem. To reduce the computational complexity of directly solving the DNSRA, we decouple the optimization variables for efficient algorithm design. By this, the strategies for user association and CPU-cycle frequency are obtained in closed forms, respectively. Power allocation and subcarriers assignment are obtained by employing the successive convex approximation approach. Meanwhile, we develop a heuristic algorithm to obtain the dynamic slice request admission decision. Simulation results show that the proposed DNSRA can strike a flexible balance between the average revenue and the average delay, and can significantly increase the operator's revenue against existing schemes. [ABSTRACT FROM AUTHOR]

Network slicing has been considered as a promising candidate to provide customized services for vehicular applications that have extremely high requirements of latency and reliability. However, the high mobility of vehicles poses significant challenges to resource management in such a stochastic vehicular environment with time-varying service demands. In this paper, we develop an online network slicing scheduling strategy for joint resource block (RB) allocation and power control in vehicular networks. The long-term time-averaged total system capacity is maximized while guaranteeing strict ultra-reliable and low-latency requirements of vehicle communication links, subject to stability constraints of task queues. The formulated problem is a mixed integer nonlinear stochastic optimization problem, which is decoupled into three subproblems by leveraging Lyapunov optimization. In order to tackle this problem, we propose an online algorithm, namely JRPSV, to obtain the optimal RB allocation and power control at each time slot according to the current network state. Furthermore, rigorous theoretical analysis is conducted for the proposed JRPSV algorithm, indicating that the system capacity and the system average latency obey a $[ {{\mathcal O}({1/V}),{\mathcal O}(V)} ]$ trade-off with the control parameter $V$. Extensive simulation results are provided to validate the theoretical analysis and demonstrate the effectiveness of JRPSV as well as the impacts of various parameters. [ABSTRACT FROM AUTHOR]