Solving job shop scheduling with setup times through constraint-based iterative sampling: an experimental analysis

This paper presents a heuristic algorithm for solving a job-shop scheduling problem with sequence dependent setup times and min/max separation constraints among the activities (SDST-JSSP/max). The algorithm relies on a core constraint-based search procedure, which generates consistent orderings of activities that require the same resource by incrementally imposing precedence constraints on a temporally feasible solution. Key to the effectiveness of the search procedure is a conflict sampling method biased toward selection of most critical conflicts and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This constraint-based search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically both on a set of previously studied job-shop scheduling benchmark problems with sequence dependent setup times and by introducing a new benchmark with setups and generalized precedence constraints.     

Performance of One-Round Walks in Linear Congestion Games

We investigate the approximation ratio of the solutions achieved after a one-round walk in linear congestion games. We consider the social functions Sum, defined as the sum of the players’ costs, and Max, defined as the maximum cost per player, as a measure of the quality of a given solution. For the social function Sum and one-round walks starting from the empty strategy profile, we close the gap between the upper bound of \(2+\sqrt{5}\approx 4.24\) given in Christodoulou et al. (Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS), LNCS, vol. 3884, pp. 349–360, Springer, Berlin, 2006) and the lower bound of 4 derived in Caragiannis et al. (Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP), LNCS, vol. 4051, pp. 311–322, Springer, Berlin, 2006) by providing a matching lower bound whose construction and analysis require non-trivial arguments. For the social function Max, for which, to the best of our knowledge, no results were known prior to this work, we show an approximation ratio of \(\Theta(\sqrt[4]{n^{3}})\) (resp. \(\Theta(n\sqrt{n})\)), where n is the number of players, for one-round walks starting from the empty (resp. an arbitrary) strategy profile.     

HLA_ACTOR_REPAST: An approach to distributing RePast models for high-performance simulations

RePast is a popular agent toolkit with proven capabilities to fulfil the modelling challenges of large multi-agent systems (MASs). The toolkit, though, is normally used on a standalone workstation and therefore its practical use can be constrained (in space and time) by the limited available computing resources. This paper proposes an original approach – HLA_ACTOR_REPAST – aimed to distributing RePast models for high-performance simulation of complex scalable models. Novel in HLA_ACTOR_REPAST is an exploitation of a lean actor infrastructure implemented in Java. Actors bring to RePast agents such features as migration, location-transparent naming, efficient communications, and a control-centric framework. Actors can be orchestrated by an in-the-large custom control structure which is in charge of ensuring the necessary message causality constraints. Distribution and time management concerns depend on the IEEE standard HLA middleware. The paper first discusses details of the software engineering process underlying the development of HLA_ACTOR_REPAST. The mapping techniques, assisted by Java text annotations and aspect-oriented programming, try to minimize “code intrusions” in the original model and favour model transparency. The paper then furnishes some experimental data which witness the good performance results achieved by applying HLA_ACTOR_REPAST to a distributed version of a classic MAS benchmark model.     

A Formal Logic Approach to Constrained Combinatorial Testing

Combinatorial testing is as an effective testing technique to reveal failures in a given system, based on input combinations coverage and combinatorial optimization. Combinatorial testing of strength t (t ≥ 2) requires that each t-wise tuple of values of the different system input parameters is covered by at least one test case. Combinatorial test suite generation algorithms aim at producing a test suite covering all the required tuples in a small (possibly minimal) number of test cases, in order to reduce the cost of testing. The most used combinatorial technique is the pairwise testing (t = 2) which requires coverage of all pairs of input values. Constrained combinatorial testing takes also into account constraints over the system parameters, for instance forbidden tuples of inputs, modeling invalid or not realizable input values combinations. In this paper a new approach to combinatorial testing, tightly integrated with formal logic, is presented. In this approach, test predicates are used to formalize combinatorial testing as a logical problem, and an external formal logic tool is applied to solve it. Constraints over the input domain are expressed as logical predicates too, and effectively handled by the same tool. Moreover, inclusion or exclusion of select tuples is supported, allowing the user to customize the test suite layout. The proposed approach is supported by a prototype tool implementation and results of experimental assessment are also presented.     

On the Convergence of Multicast Games in Directed Networks

We investigate the convergence of the price of anarchy after a limited number of moves in the classical multicast communication game when the underlying communication network is directed. Namely, a subset of nodes of the network are interested in receiving the transmission from a given source node and can share the cost of the used links according to fixed cost sharing methods. At each step, a single receiver is allowed to modify its communication strategy, that is to select a communication path from the source, and assuming a selfish or rational behavior, it will make a best response move, that is it will select a solution yielding the minimum possible payment or shared cost. We determine lower and upper bounds on the price of anarchy, that is the highest possible ratio among the overall cost of the links used by the receivers and the minimum possible cost realizing the required communications, after a limited number of moves under the fundamental Shapley cost sharing method. In particular, assuming that the initial set of connecting paths can be arbitrary, we show an $O(r\sqrt{r})We investigate the convergence of the price of anarchy after a limited number of moves in the classical multicast communication game when the underlying communication network is directed. Namely, a subset of nodes of the network are interested in receiving the transmission from a given source node and can share the cost of the used links according to fixed cost sharing methods. At each step, a single receiver is allowed to modify its communication strategy, that is to select a communication path from the source, and assuming a selfish or rational behavior, it will make a best response move, that is it will select a solution yielding the minimum possible payment or shared cost. We determine lower and upper bounds on the price of anarchy, that is the highest possible ratio among the overall cost of the links used by the receivers and the minimum possible cost realizing the required communications, after a limited number of moves under the fundamental Shapley cost sharing method. In particular, assuming that the initial set of connecting paths can be arbitrary, we show an O(r?r)O(r\sqrt{r}) upper bound on the price of anarchy after 2 rounds, during each of which all the receivers move exactly once, and a matching lower bound, that we also extend to W(r^k?{r})\Omega(r\sqrt[k]{r}) for any number k≥2 rounds, where r is the number of receivers. Similarly, exactly matching upper and lower bounds equal to r are determined for any number of rounds when starting from the empty state in which no path has been selected. Analogous results are obtained also with respect to other three natural cost sharing methods considered in the literature, that is the egalitarian, path-proportional and egalitarian-path proportional ones. Most results are also extended to the undirected case in which the communication links are bidirectional.     

A network of pyramidal neurons is sensitive to the timing of its excitatory inputs

The transmission of excitatory inputs by a network of coupled pyramidal cells is investigated by means of numerical simulations. The pyramidal cell models are coupled by excitatory synapses and each one receives an excitatory pulse at a random time extracted from a Gaussian distribution. Moreover, each cell model is injected with a noisy current. It was found that the excitatory coupling promotes the transmission of the synaptic inputs on a time scale of a few ms.     

The phase behavior of n-alkane systems

Normal alkanes show very complicated phase transition kinetics and macroscopic phase equilibrium behavior. This paper focuses on the phase stability and equilibrium of complicated mixtures like n-alkanes and on the enabling global optimization technologies needed to gather problem knowledge. The new ideas contained in this paper include:

(1) novel level set methods for gathering encoded knowledge;

(2) the differential geometry for uncovering pathways to more subtle knowledge;

(3) all supporting non-linearly constrained optimization techniques;

(4) all data handling needed to unravel complex solution structure.

These new ideas are incorporated within the integral path methodology or terrain methods recently developed by Lucia, A., & Yang, F. (2003) [Lucia, A., & Yang F. (2003). Multivariable terrain methods. AIChE Journal 49, 2553] and Lucia, DiMaggio, and Depa (2004) [Lucia, A., DiMaggio, P.A., & Depa, P. (2004). A geometric terrain methodology for global optimization. Journal of Global Optimization 29, 297]. This framework provides global knowledge for understanding solution structure, like the complex solution structure of n-alkanes. In particular, it is shown that knowledge of the Newton and tangent vector fields, Gauss curvature, integral path bifurcation points, and non-differentiable manifolds provides a deterministic way of finding additional solutions, saddle points, and other information that might otherwise go undetected.It is shown that the optimization tools developed in this work provide all knowledge of interest on the appropriate hypothetical single-phase or composite surface (i.e., minima, saddle points, singular points, and integral paths) in phase stability applications. This knowledge can be obtained by solving the phase stability problem exactly once, in a pre-processing step, and used to reliably initialize any multi-phase equilibrium calculation for any feed. This removes the need to repeatedly solve the phase stability problem as the feed composition changes and greatly increases computational efficiency. Numerical examples and geometric illustrations are used to elucidate key ideas and to show how the proposed approach can be used to unravel the complicated phase behavior of n-alkane mixtures.     

Minimize the Maximum Duty in Multi-interface Networks

We consider devices equipped with multiple wired or wireless interfaces. By switching of various interfaces, each device might establish several connections. A connection is established when the devices at its endpoints share at least one active interface. Each interface is assumed to require an activation cost. In this paper, we consider two basic networking problems in the field of multi-interface networks. The first one, known as the Coverage problem, requires to establish the connections defined by a network. The second one, known as Connectivity problem, requires to guarantee a connecting path between any pair of nodes of a network. Both are subject to the constraint of keeping as low as possible the maximum cost set of active interfaces at each single node. We study the problems of minimizing the maximum cost set of active interfaces among the nodes of the network in order to cover all the edges in the first case, or to ensure connectivity in the second case. We prove that the Coverage problem is NP-hard for any fixed Δ≥5 and k≥16, with Δ being the maximum degree, and k being the number of different interfaces among the network. We also show that, unless P=NP, the problem cannot be approximated within a factor of ηln?Δ, for a certain constant η. We then provide a general approximation algorithm which guarantees a factor of O((1+b)ln?Δ), with b being a parameter depending on the topology of the input graph. Interestingly, b can be bounded by a constant for many graph classes. Other approximation and exact algorithms for special cases are presented. Concerning the Connectivity problem, we prove that it is NP-hard for any fixed Δ≥3 and k≥10. Also for this problem, the inapproximability result holds, that is, unless P=NP, the problem cannot be approximated within a factor of ηln?Δ, for a certain constant η. We then provide approximation and exact algorithms for the general problem and for special cases, respectively.     

High‐quality pagination for publishing

The problem of line breaking consists of finding the best way to split paragraphs into lines. It has been cleverly addressed by the total‐fit algorithm exposed by Knuth and Plass in a well‐known paper. Similarly, page‐breaking algorithms break the content flow of a document into page units. Formatting languages—such as the World Wide Web Consortium standard Extensible Stylesheet Language Formatting Objects (XSL‐FO)—allow users to set which content should be kept in the same page and how many isolated lines are acceptable at the beginning/end of each page. The strategies most formatters adopt to meet these requirements, however, are not satisfactory for many publishing contexts as they very often generate unpleasant empty areas. In that case, typographers are required to manually craft the results in order to completely fill pages. This paper presents a page‐breaking algorithm that extends the original Knuth and Plass line‐breaking approach and produces high‐quality documents without unwanted empty areas. The basic idea consists of delaying the definitive choice of breaks in the line‐breaking process in order to provide a larger set of alternatives to the actual pagination step. The algorithm also allows users to decide the set of properties to be adjusted for pagination and their variation ranges. An application of the algorithm to XSL‐FO is also presented, with an extension of the language that allows users to drive the pagination process. The tool, named FOP+, is a customized version of the open‐source Apache Formatting Objects Processor formatter. Copyright © 2011 John Wiley & Sons, Ltd.     

Mechanical sensorless speed control of permanent-magnet AC motors driving an unknown load

A new sensorless scheme for high-performance speed control of permanent-magnet ac motors (PMACMs) driving an unknown load is proposed. This scheme uses an extended nonlinear reduced-order observer to estimate the induced electromotive force (EMF) and load torque. From the estimated variables, the rotor position, the rotor speed, and the position derivative of flux are calculated and are used to close the control loop. In order to improve the drive performance, the estimated load torque is incorporated as a feedforward signal in the closed control loop. In addition, the proposed sensorless PMACM drive allows the torque-ripple and copper-loss minimization for motors with an arbitrary EMF waveform. Simulation and experimental results to validate the proposal are presented in this paper.