Search

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]

Two-level priority based assignment problem (2PBAP) is an important optimization problem due to the timely delivery requirement in project management. Only four methods with deficiency are available in the literature to solve 2PBAP. In this paper, 2PBAP is reduced to a series of finding the feasible flow in a network with lower and upper arc capacities, and consequently two iterative algorithms are developed to solve 2PBAP. It is proved that both iterative algorithms find the optimal solution to 2PBAP in a strongly polynomial time. Owing to having fully utilized the network flow structural characteristic inherent to 2PBAP, both iterative algorithms have the advantages such as easy implementation on computer, no memory overflow in implementation on computer for large scale instances, high computational efficiency, and easy extension to the priority based assignment problem with priority level more than two, and successfully overcome the deficiency of existing approaches. Computational experiments validate that in terms of computational time, one of our proposed iterative algorithms has higher efficiency than the other, and rivals the existing best approach. [ABSTRACT FROM AUTHOR]

Uncertain random simulation plays an important role in solving uncertain random optimization problems that include random variables and uncertain variables. In this paper, an uncertain random simulation is proposed and developed to obtain the chance distribution, α -pessimistic value and α -optimistic value. Further, an α -optimal model for the uncertain random bottleneck assignment problem under the Hurwicz criterion is presented. Finally, a numerical example is given to illustrate how to use the proposed simulation algorithm to solve an uncertain random bottleneck assignment problem. [ABSTRACT FROM AUTHOR]

Abstract: This paper proposes modified particle swarm optimization to solve the problem of activity assignment of fourth party logistics (4PL) with preemptive structure. In practice, decision makers must consider goals of different importance when they encounter 4PL decision problems. Previous studies have adopted weighted fuzzy goal programming to design optimization problems. However, it is difficult for decision makers to determine proper weights. This paper proposes a decision making method based on preemptive fuzzy goal programming and a modified PSO. The proposed method does not require weights, and prevents results without feasible solutions caused by improper resource setting. Furthermore, this paper proposes a modified PSO with mutation operator extension. Numerical analysis shows that proposed modified PSOs prevent algorithms from caving prematurely into local optimums. [Copyright &y& Elsevier]

In this paper we propose a generalization of the Assignment Problem. First, we describe an algorithm, based on network flow techniques, that obtains just one solution of the approached problem; further, we develop an algorithm that is able to find all the solutions. Finally, we discuss how this general form of the Assignment Problem can be applied in solving the Rank Aggregation Problem, in the case of rankings with ties. [ABSTRACT FROM AUTHOR]

In this paper we discuss the shortest augmenting path method for solving assignment problems in the following respect: — we introduce this basic concept using matching theory; — we present several efficient labeling techniques for constructing shortest augmenting paths; — we show the relationship of this approach to several classical assignment algorithms; — we present extensive computational experience for complete problems, and — we show how postoptimal analysis can be performed using this approach and naturally leads to a new, highly efficient hybrid approach for solving large-scale dense assignment problems. [ABSTRACT FROM AUTHOR]

Periodic global updates of dual variables have been shown to yield a substantial speed advantage in implementations of push-relabel algorithms for the maximum flow and minimum cost flow problems. In this paper, we show that in the context of the bipartite matching and assignment problems, global updates yield a theoretical improvement as well. For bipartite matching, a push-relabel algorithm that uses global updates runs in O(√nm &frac log(N² /m) / log n;time (matching the best bound known) and performs worse by a factor of √n without the updates. A similar result holds for the assignment problem, for which an algorithm that assumes integer costs in the range [- C, …, C] and that runs in time O(√nm log(nC)) (matching the best cost-scaling bound known) is presented. [ABSTRACT FROM AUTHOR]

We generalize the well-known primal-dual algorithm proposed by Chambolle and Pock for saddle point problems and relax the condition for ensuring its convergence. The relaxed convergenceguaranteeing condition is effective for the generic convex setting of saddle point problems, and we show by the canonical convex programming problem with linear equality constraints that the relaxed condition is optimal. It also allows us to discern larger step sizes for the resulting subproblems, and thus provides a simple and universal way to improve numerical performance of the original primal-dual algorithm. In addition, we present a structure-exploring heuristic to further relax the convergence-guaranteeing condition for some specific saddle point problems, which could yield much larger step sizes and hence significantly better performance. Effectiveness of this heuristic is numerically illustrated by the classic assignment problem. [ABSTRACT FROM AUTHOR]

The Assignment Problem is a classical problem in the field of combinatorial optimization, having a wide range of applications in a variety of contexts. In general terms, the Assignment Problem consists of determining the best assignment of tasks to agents according to a predefined objective function. Different variants of the Assignment Problem have been extensively investigated in the literature in the last 50 years. In this work, we introduce and analyze the problem of optimizing a business process model with the objective of finding the most beneficial assignment of tasks to agents. Despite similarities, this problem is distinguished from the traditional Assignment Problem in that we consider tasks to be part of a business process model, being interconnected according to defined rules and constraints. In other words, assigning a business process to agents is a more complex form of the Assignment Problem. Two main categories of business processes, assignment-independent and assignment-dependent, are distinguished. In the first category, different assignments of tasks to agents do not affect the flow of the business process, while processes in the second category contain critical tasks that may change the workflow, depending on who performs them. In each category several types of processes are studied. Algorithms for finding optimal and near-optimal solutions to these categories are presented. For the first category, depending on the type of process, the Hungarian algorithm is combined with either the analytical method or simulation to provide an optimal solution. For the second category, we introduce two algorithms. The first one finds an optimal solution, but is feasible only when the number of critical tasks is small. The second algorithm is applicable to large number of critical tasks, but provides a near-optimal solution. In the second algorithm a hill-climbing heuristic method is combined with the Hungarian algorithm and simulation to find an overall near-optimal solution. A series of tests is conducted which demonstrates that the proposed algorithms efficiently find optimal solutions for assignment-independent and near-optimal solutions for assignment-dependent processes. [ABSTRACT FROM AUTHOR]

Abstract: This paper concentrates on sensitivity analysis of the fuzzy assignment problem (FAP). Since most real environments are uncertain, the FAP is more realistic than the assignment problem in application. Owing to the high degeneracy of the FAP, as that of the assignment problem, traditional sensitivity analysis, called Type I sensitivity analysis, which determines the range in which the current optimal basis remains optimal, is impractical. Hence, we attempt to perform other two types of advanced sensitivity analysis, called Type II and Type III sensitivity analysis, to overcome this problem. A labeling algorithm is then presented, where Type II sensitivity analysis is to determine the range of perturbation to keep the current optimal assignment remaining optimal, and Type III sensitivity analysis is to determine the range for which the rate of change of optimal value function remains unchanged. The procedure of the labeling algorithm is divided into two parts: one is when the unassigned cell is perturbed, and the other is when the assigned cell is perturbed. An example is presented to demonstrate that the labeling algorithm is a useful tool for determining the Type II and Type III sensitivity analysis of the FAP. [Copyright &y& Elsevier]

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

Abstract: An efficient exterior point simplex type algorithm for the assignment problem has been developed by Paparrizos [K. Paparrizos, An infeasible (exterior point) simplex algorithm for assignment problems, Math. Program. 51 (1991) 45–54]. This algorithm belongs to the category of forest algorithms and solves an assignment problem in at most iterations and in at most time. In this paper worst case examples are presented. Specifically, a systematic procedure to construct worst case assignment problems is presented for the exterior point algorithm. The algorithm applied to these examples executes exactly iterations. This result verifies that the bound is the best possible for the above-mentioned algorithm. [Copyright &y& Elsevier]

This note formulates an assignment problem for obtaining optimal level schedules for mixed-model assembly lines in JIT production systems. The problem was formulated as a quadratic integer programming problem in a recent paper by Miltenburg (1989) where, however, only enumerative algorithms and heuristics were proposed for its solution. Our assignment formulation can also be extended to more general objective functions than the one used by Miltenburg. [ABSTRACT FROM AUTHOR]

We consider a due-window assignment problem on identical parallel machines, where the jobs have equal processing times and job-dependent earliness-tardiness costs. We would like to determine a 'due window' during which the jobs can be completed at no cost and to obtain a job schedule in which the jobs are penalized if they finish before or after the due window. The objective is to minimize the total earliness and tardiness job penalty, plus the cost associated with the size of the due window. We present an algorithm that can solve this problem in O(n3) time, which is an improvement of the O(n4) solution procedure developed by Mosheiov and Sang. [ABSTRACT FROM AUTHOR]

The article presents a study which proposes a new hierarchical method for the flexible job-shop scheduling problem (FJSP). The FJSP is a nondeterministic polynomial-time hard since it is an extension of the job-shop scheduling problem. The first method proposed is based successively on a heuristic approach and a local search. The second one is based on a branch-and-bound algorithm.