An exact algorithm for Min-Max hyperstructure equipartition with a connected constraint

Hyperstructure is a topological concept that shares characteristics with both graphs and hypergraphs. The Min-Max hyperstructure equipartition with a connected constraint problem consists in partitioning a hyperstructure into K equal-sized connected parts that minimizes the maximum load in each part (the number of hyperedges assigned to each part). This problem, proved to be NP-hard, is an integer nonlinear programming problem. The linearized version of this problem has been introduced.Shrink and Cut algorithm is designed to simplify original complex hyperstructure without changing the optimal solution of the Min-Max hyperstructure equipartition with a connected constraint problem. By the use of this algorithm, Min-Max hyper-tree equipartition with a connected constraint can be solved in polynomial time. An exact algorithm: Min-Max hyperstructure partitioning algorithm, based on a Shrink and Cut algorithm and algorithm S for finding all the spanning trees, is designed to solve ordinary cases, which shows well on experimental results.     

Deterministic annealing with Potts neurons for multi-robot routing

A deterministic annealing (DA) method is presented for solving the multi-robot routing problem with min–max objective. This is an NP-hard problem belonging to the multi-robot task allocation set of problems where robots are assigned to a group of sequentially ordered tasks such that the cost of the slowest robot is minimized. The problem is first formulated in a matrix form where the optimal solution of the problem is the minimum-cost permutation matrix without any loops. The solution matrix is then found using the DA method is based on mean field theory applied to a Potts spin model which has been proven to yield near-optimal results for NP-hard problems. Our method is bench-marked against simulated annealing and a heuristic search method. The results show that the proposed method is promising for small-medium sized problems in terms of computation time and solution quality compared to the other two methods.

     

Multi-device task offloading with time-constraints for energy efficiency in mobile cloud computing

Nowadays, in order to deal with the increasingly complex applications on mobile devices, mobile cloud offloading techniques have been studied extensively to meet the ever-increasing energy requirements. In this study, an offloading decision method is investigated to minimize the energy consumption of mobile device with an acceptable time delay and communication quality. In general, mobile devices can execute a sequence of tasks in parallel. In the proposed offloading decision method, only parts of the tasks are offloaded for task characteristics to save the energy of multi-devices. The issue of the offloading decision is formulated as an NP-hard 0–1 nonlinear integer programming problem with time deadline and transmission error rate constraints. Through decision-variable relaxation from the integer to the real domain, this problem can be transformed as a continuous convex optimization. Based on Lagrange duality and the Karush–Kuhn–Tucker condition, a solution with coupled terms is derived to determine the priority of tasks for offloading. Then, an iterative decoupling algorithm with high efficiency is proposed to obtain near-optimal offloading decisions for energy saving. Simulation results demonstrate that considerable energy can be saved via the proposed method in various mobile cloud scenarios.     

A comparison of human and near-optimal task management behavior

OBJECTIVE: The primary contribution of this work is the development of an abstract framework to which a variety of multitasking scenarios can be mapped. The metaphor of a juggler spinning plates was introduced to represent an operator performing multiple concurrent tasks. BACKGROUND: This allowed seeking a quantitative model for management of multiple continuous tasks instead of a model for completing multiple discrete tasks, which was considered in previous studies. METHODS: The multitasking performance of 10 participants in five scenarios was measured in a low-fidelity simulator (named Tardast), which was developed based on the concept of the juggler metaphor. This performance was then compared with a normative model, which was a near-optimal solution to a mathematical programming problem found by tabu search heuristics. RESULTS: Tabu outperformed the participants overall, although the best individual performance nearly equaled that of tabu. It was also observed that participants initially tended to manage numerous tasks poorly but that they gradually learned to handle fewer tasks and excel in them. CONCLUSION: This suggests that they initially overreacted to the penalization associated with poor performance in the software. Participants' strategic task management (e.g., what tasks to handle) was more significant in obtaining a good score than their tactical task management (e.g., how often to switch between two tasks). APPLICATION: Potential applications include better design of equipment, procedures, and training of operators of complex systems.     

Models for a traveling purchaser problem with additional side-constraints

The traveling purchaser problem (TPP) is the problem of determining a tour of a purchaser that needs to buy several items in different shops such that the total amount of travel and purchase costs is minimized. Motivated by an application in machine scheduling, we study a variant of the problem with additional constraints, namely, a limit on the maximum number of markets to be visited, a limit on the number of items bought per market and where only one copy per item needs to be bought. We present an integer linear programming (ILP) model which is adequate for obtaining optimal integer solutions for instances with up to 100 markets. We also present and test several variations of a Lagrangian relaxation combined with a subgradient optimization procedure. The relaxed problem can be solved by dynamic programming and can also be viewed as resulting from applying a state space relaxation technique to a dynamic programming formulation. The Lagrangian based method is combined with a heuristic that attempts to transform relaxed solutions into feasible solutions. Computational results for instances with up to 300 markets show that with the exception of a few cases, the reported differences between best upper bound and lower bound values on the optimal solutions are reasonably small.     

Solving the maximal covering location problem with heuristic concentration

The metaheuristic heuristic concentration (HC) is applied here to the solution of large instances of the maximal covering location problem with high percentage coverage. In these instances, exact methods may be too cumbersome for practical use, and heuristics can allow faster solution times with near-optimal results. We examined the performance of HC based on its ability to approach the optimal solutions to these problems and the run times of the algorithm compared to LP-IP runtimes. Exact solutions, generated by linear programming and branch and bound, provided a benchmark for comparison when the LP-IP problems could be run to completion. In all cases, HC found solutions with objective values no worse than 0.543% below the best known LP-IP objective value. In several instances, LP-IP runtime ballooned to as much as 38.5 h, while HC took no longer than 1.6 h in any instance. In one particular instance, LP-IP took 38.5 h to terminate, while HC found a near-optimal solution (within 0.306% of optimality) in only 25 min. Furthermore, in 62.5% of the runs, the second stage of HC improved on the first stage 1-opt algorithm.     

基于自组织优化算法的一类多旅行商问题

多旅行商问题作为旅行商问题的一个扩展,是一个经典的组合优化问题,具有更高的复杂性,也具有更广泛的实际意义。针对每个旅行商允许经过的城市数有上限的多旅行商问题,通过引入虚拟城市把多旅行商问题转化为单旅行商问题,并且应用自组织优化算法进行了求解。虚拟城市局部适值的定义很好地处理了此类问题的能力约束,针对多旅行商问题的实例进行的仿真表明自组织优化算法可以很好地求解此类问题。     

计算集群中一种基于任务运行时间的组合预测方案

针对现有单一预测策略不适用于所有异构任务的问题,提出一种基于本地任务与远程任务运行时间的组合预测方案(CPS)和预测精度保证(PAA)的概念。使用GridSim工具集来实现CPS,将PAA作为定量评价由某一特定预测策略提供的预测运行时间精度的标准。仿真实验表明:与本地任务预测策略如Last和滑动窗口中值(SM)相比,CPS的平均相对残差下降了1.58%、1.62%;与远程任务预测策略如平均运行时间(RM)和加权移动平均值(ES)相比,CPS的平均相对残差下降了1.02%、2.9%。因此,PAA能从综合策略所提供的结果中选择接近最优值的预测,CPS增强了计算环境中本地任务和远程任务运行时间的PAA。     

Probabilistic incremental program evolution

Probabilistic incremental program evolution (PIPE) is a novel technique for automatic program synthesis. We combine probability vector coding of program instructions, population-based incremental learning, and tree-coded programs like those used in some variants of genetic programming (GP). PIPE iteratively generates successive populations of functional programs according to an adaptive probability distribution over all possible programs. Each iteration, it uses the best program to refine the distribution. Thus, it stochastically generates better and better programs. Since distribution refinements depend only on the best program of the current population, PIPE can evaluate program populations efficiently when the goal is to discover a program with minimal runtime. We compare PIPE to GP on a function regression problem and the 6-bit parity problem. We also use PIPE to solve tasks in partially observable mazes, where the best programs have minimal runtime.     

Some notes on maximal arc intersection of spherical polygons: its \mathcal{NP} -hardness and approximation algorithms

Finding a sequence of workpiece orientations such that the number of setups is minimized is an important optimization problem in manufacturing industry. In this paper we present some interesting notes on this optimal workpiece setup problem. These notes show that (1) The greedy algorithm proposed in Comput. Aided Des. 35 (2003), pp. 1269–1285 for the optimal workpiece setup problem has the performance ratio bounded by O(ln n−ln ln n+0.78), where n is the number of spherical polygons in the ground set; (2) In addition to greedy heuristic, linear programming can also be used as a near-optimal approximation solution; (3) The performance ratio by linear programming is shown to be tighter than that of greedy heuristic in some cases.     

Efficient Management of Multi-Linked Negotiation Based on a Formalized Model

A Multi-linked negotiation problem occurs when an agent needs to negotiate with multiple other agents about different subjects (tasks, conflicts, or resource requirements), and the negotiation over one subject has influence on negotiations over other subjects. The solution of the multi-linked negotiations problem will become increasingly important for the next generation of advanced multi-agent systems. However, most current negotiation research looks only at a single negotiation and thus does not present techniques to manage and reason about multi-linked negotiations. In this paper, we first present a technique based on the use of a partial-order schedule and a measure of the schedule, called flexibility, which enables an agent to reason explicitly about the interactions among multiple negotiations. Next, we introduce a formalized model of the multi-linked negotiation problem. Based on this model, a heuristic search algorithm is developed for finding a near-optimal ordering of negotiation issues and their parameters. Using this algorithm, an agent can evaluate and compare different negotiation approaches and choose the best one. We show how an agent uses this technology to effectively manage interacting negotiation issues. Experimental work is presented which shows the efficiency of this approach.     

Models and algorithms for competitive facility location problems with different customer behavior

Competitive facility location problems arise in the context of two non-cooperating companies, a leader and a follower, competing for market share from a given set of customers. We assume that the firms place a given number of facilities on locations taken from a discrete set of possible points. For this bi-level optimization problem we consider six different customer behavior scenarios from the literature: binary, proportional and partially binary, each combined with essential and unessential demand. The decision making for the leader and the follower depends on these scenarios. In this work we present mixed integer linear programming models for the follower problem of each scenario and use them in combination with an evolutionary algorithm to optimize the location selection for the leader. A complete solution archive is used to detect already visited candidate solutions and convert them efficiently into similar, not yet considered ones. We present numerical results of our algorithm and compare them to so far state-of-the-art approaches from the literature. Our method shows good performance in all customer behavior scenarios and is able to outperform previous solution procedures on many occasions.     

上下层具有合作关系的两层决策问题研究

针对两层线性规划问题解的无效性,在决策者合作情形下,利用双准则线性规划的有关技术,提出事先不需求解问题而是采用次最优解作为参考点,直接在目标集中有效满意解的方法。数值计算结果表明该方法有效可行的。     

A model for line capacity design for PWB assembly systems

In a multi-product, flexible manufacturing environment, line capacity of printed wiring board (PWB) assembly systems may need to be designed at the beginning of each aggregate planning period because of demand fluctuation over multiple periods. A model of line capacity design problem and production planning at the aggregate level is developed, in which production and subcontracting are assumed to be two options for a firm to meet market demand. The model presented is a large-scale integer programming problem, it cannot be solved by using standard- or mixed-integer programming codes. Under the assumption that each machine line is dedicated to produce one product family, the model can be decomposed as a relatively small subproblem, and each subproblem has good properties by which the subproblems can be further simplified and decomposed over multiple planning periods. As the result, the original large-scale two-stage integer programming problem can be approximately solved by solving a series of small-scale mixed-integer programming, which can be implemented on a workstation or a PC. Computational studies show that the solution method is developed which gives near-optimal solutions with much less computational effort.     

A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs

This work deals with a class of problems under interval data uncertainty, namely interval robust-hard problems, composed of interval data min-max regret generalizations of classical NP-hard combinatorial problems modeled as 0-1 integer linear programming problems. These problems are more challenging than other interval data min-max regret problems, as solely computing the cost of any feasible solution requires solving an instance of an NP-hard problem. The state-of-the-art exact algorithms in the literature are based on the generation of a possibly exponential number of cuts. As each cut separation involves the resolution of an NP-hard classical optimization problem, the size of the instances that can be solved efficiently is relatively small. To smooth this issue, we present a modeling technique for interval robust-hard problems in the context of a heuristic framework. The heuristic obtains feasible solutions by exploring dual information of a linearly relaxed model associated with the classical optimization problem counterpart. Computational experiments for interval data min-max regret versions of the restricted shortest path problem and the set covering problem show that our heuristic is able to find optimal or near-optimal solutions and also improves the primal bounds obtained by a state-of-the-art exact algorithm and a 2-approximation procedure for interval data min-max regret problems.     

A field-based versus a protocol-based approach for adaptive task assignment

Task assignment in multi-agent systems is a complex coordination problem, in particular in systems that are subject to dynamic and changing operating conditions. To enable agents to deal with dynamism and change, adaptive task assignment approaches are needed. In this paper, we study two approaches for adaptive task assignment that are characteristic for two classical families of task assignment approaches. FiTA is a field-based approach in which tasks emit fields in the environment that guide idle agents to tasks. DynCNET is a protocol-based approach that extends Standard Contract Net (CNET). In DynCNET, agents use explicit negotiation to assign tasks. We compare both approaches in a simulation of an industrial automated transportation system. Our experiences show that: (1) the performance of DynCNET and FiTA are similar, while both outperform CNET; (2) the complexity to engineer DynCNET is similar to FiTA but much more complex than CNET; (3) whereas task assignment with FiTA is an emergent solution, DynCNET specifies the interaction among agents explicitly allowing engineers to reason on the assignment of tasks, (4) FiTA is inherently robust to message loss while DynCNET requires substantial additional support. The tradeoff between (3) and (4) is an important criteria for the selection of an adaptive task assignment approach in practice.     

Synchronization of decentralized multiple-model systems by market-based optimization.

Market-based optimization is a new optimization method for large decentralized systems where the distributed resource allocation of an economic system is adopted. Market-based algorithms can be interpreted as multi-agent scenarios where producer and consumer agents both compete and cooperate on a market of specified commodities. The market-based approach is applied to the synchronization of a set of local multiple-model systems. The method is extended to the case where each of the subsystems is represented by a Takagi-Sugeno (TS) fuzzy system. Although all local systems are provided with the same control input, the behaviors of the local systems are, in general, different because of different parameters in the subsystems. The task of the market-based optimization is to find an appropriate composition of subsystems so that all local systems exhibit a similar dynamical behavior. Examples show that even systems with potentially unstable local systems can be synchronized if there exists a stable combination of weighted subsystems.     

A high‐productivity task‐based programming model for clusters

Programming for large‐scale, multicore‐based architectures requires adequate tools that offer ease of programming and do not hinder application performance. StarSs is a family of parallel programming models based on automatic function‐level parallelism that targets productivity. StarSs deploys a data‐flow model: it analyzes dependencies between tasks and manages their execution, exploiting their concurrency as much as possible. This paper introduces Cluster Superscalar (ClusterSs), a new StarSs member designed to execute on clusters of SMPs (Symmetric Multiprocessors). ClusterSs tasks are asynchronously created and assigned to the available resources with the support of the IBM APGAS runtime, which provides an efficient and portable communication layer based on one‐sided communication. We present the design of ClusterSs on top of APGAS, as well as the programming model and execution runtime for Java applications. Finally, we evaluate the productivity of ClusterSs, both in terms of programmability and performance and compare it to that of the IBM X10 language. Copyright © 2012 John Wiley & Sons, Ltd.     

A preference processing model for cooperative agents

When multiple valid solutions are available to a problem, preferences can be used to indicate a choice. In a distributed system, such a preference-based solution can be produced autonomous agents cooperating together, but the attempt will lead to contention if the same resource is given preference by several user-agents. To resolve such contentions, this paper proposes a market-based payment scheme for selling and buying preferences by the contenders, in which the best solution is defined as the one where as many preferences as theoretically possible are globally met. After exploring the nature of preference, the paper develops a preference processing model based on the market based scheme, and presents a theoretical performance model to verify the correctness of the processing model. This verification is provided by a simulation study of the processing model. For the simulation study, a manufacturing environment is conjectured, where a set of tasks are resolved into subtasks by coordinator agents, and then these subtasks are allocated to assembler agents through cooperation and negotiation, in which preferred resources are exchanged against payments. The study shows that our agent based strategy not only produces convergence on the total preference value for the whole system, but also reaches that final value irrespective of the initial orderof subtask allocation to the assemblers.     

Improved Task and Resource Partitioning Under the Resource-Oriented Partitioned Scheduling

Coordinated partitioning and resource sharing have attracted considerable research interest in the field of real-time multiprocessor systems. However, finding an optimal partition is widely known as NP-hard, even for independent tasks. A recently proposed resource-oriented partitioned (ROP) fixed-priority scheduling that partitions tasks and shared resources respectively has been shown to achieve a non-trivial speedup factor guarantee, which promotes the research of coordinated scheduling to a new level. Despite the theoretical elegance, the schedulability performance of ROP scheduling is restricted by the heuristic partitioning methods used in the original study. In this paper, we address the partitioning problem for tasks and shared resources under the ROP scheduling. A unified schedulability analysis framework for the ROP scheduling is proposed in the first place. A sophisticated partitioning approach based on integer linear programming (ILP) is then proposed based on the unified analysis. Empirical results show that the proposed methods improve the schedulability of ROP scheduling significantly, and the runtime complexity for searching a solution is reduced prominently compared with other ILP-based approaches as well.