We address the problem of generating robust solutions for the makespan minimization problem on identical agents (parallel machines), under the assumption that only interval bounds of processing times are known. While there are various concepts of robustness in the literature, we prove using pathological examples that any of these criteria may result in allocations with undesirable characteristics. We identify key properties that must be satisfied for a solution to be considered truly robust. Given a set of jobs with associated loads and uncertainties, it is shown that an allocation that balances loads and uncertainties simultaneously is extremely robust and satisfies multiple other existing criteria of robustness within an acceptable approximation factor. Thus, robustness is achieved by distributing the uncertainty/risk among the agents along with the load. The problem of finding a robust allocation is reduced to a bi-criteria two-dimensional load balancing problem, with the two dimensions being the load and the uncertainty. We prove that for the case with 2 agents, an allocation that satisfies a 1.5-approximation on both dimensions simultaneously always exists and can be found efficiently, and is also the best possible guarantee. For the general case with any number of agents, we prove that an allocation that satisfies a 2-approximation on one dimension and a 2.5-approximation on the other always exists and can be found in pseudo-polynomial time. The approximation algorithms presented in this paper are complemented by interesting existential and structural results and contribute to the vector scheduling literature for two dimensions as well. Finally, an extensive numerical analysis is presented, where we demonstrate our algorithms’ near-optimal performance and ability to generate allocations that satisfy multiple criteria of robustness simultaneously in a short amount of time. Note to Practitioners—This paper introduces a simple and provably effective methodology for generating robust allocations in the context of the makespan minimization problem, a critical challenge in operational management that significantly impacts the efficiency and productivity of various industries. We demonstrate using counter-examples that traditional concepts of robustness such as worst-case makespan and min-max regret can lead to overly conservative and practically inefficient allocations, even when solved optimally. Following this, it is shown that an allocation that balances loads and uncertainties simultaneously is extremely robust and satisfies multiple other existing criteria of robustness within an acceptable approximation factor. This leads to a more attractive and practical concept of robustness. Efficient, fast, and provably good algorithms are presented that solve a 2D Load Balancing problem and generate allocations that are balanced with respect to both the loads as well as uncertainties for a large percentage of the possible scenarios. Numerical results provide practitioners confidence in our approach. The algorithm further classifies the jobs as critical and non-critical based on their completion times and uncertainties in a way that leads to provably good allocations. This classification can be further used to obtain intuition about the problem, thus providing managerial insights.

We study the problem of allocating a set of indivisible operations to a set of agents in a fair and efficient manner while also minimizing the makespan. We first present the Operation Trading Algorithm that generates allocations satisfying the DEQx (Duplicated Equitability up to any operation) fairness criterion while also guaranteeing an upper bound of 2 on the makespan for identical agents. The pairwise approach used in this algorithm has the added advantages of being decentralizable and robust. We then define a relaxed version of the DEQ1 (Duplicated Equitability upto some operation) fairness criterion called partial-DEQ1. A market based algorithm is presented to achieve partial-DEQ1 along with Pareto Optimality. Following this, it is shown that the algorithm also guarantees an upper bound of 1.618 on the makespan for 2 non-identical agents. Parametric Pruning further improves the upper bound to 1.5 which is theoretically the best possible upper bound. To the best of our knowledge, these are the first algorithms designed to achieve the mentioned fairness criteria. The algorithms additionally guarantee upper bounds on the makespan. Finally, we show the efficacy of the algorithms in generating allocations with near optimal makespans by numerically evaluating the algorithms on random instances. Note to Practitioners—This paper provides fast algorithms that can be used for task allocation among any number of agents. The algorithms generate allocations that satisfy fairness criteria along with minimizing the makespan, thus achieving two practically important criteria simultaneously. Additionally, some of the algorithms introduced can be implemented in a reactive manner thus making it easy to deal with sudden changes. The algorithms can also be implemented in a decentralized manner in environments where maintaining a centralized situational awareness is difficult due to communication and machine failures.

It is often of interest to synthesize a supervisory policy for enforcing complex properties on the behaviour of a Discrete-Event System (DES). One way of doing this is by decomposing complex properties into simpler objectives and then synthesizing supervisors for those simpler objectives in a sequential manner. This approach is particularly convenient if the supervised-system can be represented using the same modeling framework at each stage of this sequential process. An additional desirable feature could be that the supervisory policy remain the same even if the initial-state of the DES were to change. In this paper, we consider Petri Net (PN) models of Discrete - Event Systems (DES) under a supervisory policy that enforces a desired-property B. We prove that the supervised-system can be modeled as a PN if and only if the supervisory policy is a marking-monotone-B-enforcing supervisory policy (MM-BESP) over reachable markings. In the second half of the paper we describe a software tool for the synthesis of MM-BESPs, where the desired-property B is the PN-property of liveness, for arbitrary Petri Nets. We end the paper with an example that illustrates both the contributions.

Lab kits allow students to take home laboratory equipment to complete experiments on their own time. Kits like these can expand access to hands-on experiences for online courses and to budget-strapped campuses. Although students like these kits, no previous studies compared student learning outcomes on assignments using these new kits with previous laboratory equipment. During the 2014-2015 academic year, we conducted a quasi-experiment to compare students' achievement of learning outcomes. Half of the laboratory sections in each semester used the existing equipment, while the other sections used the new kit. The objectives of the laboratory assignments were the same and the instructions were kept as close as possible between the two groups.

If there are transitions in a Petri net (PN) that cannot be prevented from firing by a supervisory policy, then we have a partially controlled PN. The existence of a liveness enforcing supervisory policy (LESP) in a partially controlled ordinary PN is undecidable. Consequently, there can be no algorithms that synthesize an LESP for an arbitrary ordinary (general) PN. In contrast, we identify a class of general free-choice PN (FCPN) structures, which strictly includes the class of ordinary FCPN structures, where the existence of an LESP in any marked member of the class is decidable.

We identify a class of partially controlled Petri net (PN) structures, which is denoted by G, that strictly includes the class of partially controlled free-choice (FC) PN structures. We show that there is a supervisory policy that enforces liveness in an arbitrary instance N(m0), where N ∈ G, if and only if there is a similar policy for an FCPN that results when the construction procedure enunciated in this paper is executed with N and its controllable transition set as input. Since the existence of a supervisory policy in an arbitrary partially controlled FCPN is decidable, it follows that the existence of similar policies for any N(m0), where N ∈ G, is also decidable. Furthermore, when it exists, the minimally restrictive supervisory policy that enforces in a member of G is characterized by a right-closed set of markings.

We consider a wireless network of n nodes that communicate over a common wireless medium under some interference constraints. Our work is motivated by the need for an efficient and distributed algorithm to determine the n2 dimensional unicast capacity region of such a wireless network. Equivalently, given a vector of end-to-end rates between various source-destination pairs, we seek to determine if it can be supported by the network through a combination of routing and scheduling decisions. This question is known to be NP-hard and hard to even approximate within n1-o(1)factor for general graphs. In this paper, we first show that the whole n2dimensional unicast capacity region can be approximated to (1 plusmn epsiv) factor in polynomial time, and in a distributed manner, whenever the Max Weight Independent Set (MWIS) problem can be approximated in a similar fashion for the corresponding topology. We then consider wireless networks which are usually formed between nodes that are placed in a geographic area and come endowed with a certain geometry, and argue that such situations do lead to approximations to the MWIS problem (in fact, in a completely distributed manner, in a time that is essentially linear in n). Consequently, this gives us a polynomial algorithm to approximate the capacity of wireless networks to arbitrary accuracy. This result hence, is in sharp contrast with previous works that provide algorithms with at least a constant factor loss. An important ingredient in establishing our result is the transient analysis of the maximum weight scheduling algorithm, which can be of interest in its own right.

Rate allocation is a fundamental problem in the operation of a wireless network because of the necessity to schedule the operation of mutually interfering links between the nodes. Among the many reasons behind the importance of efficiently determining the membership of an arbitrary rate vector in the feasibility region, is its high relevance in optimal cross layer design. A key feature in a wireless network is that links without common nodes can also conflict (secondary interference constraints). While the node exclusive model problem has efficient algorithms, it has long been known that this is a hard problem with these additional secondary constraints. However, wireless networks are usually deployed in geographic areas that do not span the most general class of all graphs possible. This is the underlying theme of this paper, where we provide algorithms for two restricted instances of wireless network topologies. In the first tractable instance, we consider nodes placed arbitrarily in a region such that (a) the node density is bounded, and (b) a node can only transmit or interfere with other nodes that are within a certain limited radius. We obtain a simple (1 - epsi) polynomial-time approximation scheme for checking feasibility (for any epsi > 0). The second instance considers the membership problem of an arbitrary rate-vector in the feasible set, where the nodes are distributed within a slab of fixed width (there are no density assumptions). Specifically, the results in [13] are shown to extend to a much more general class of graphs, which we call the (dmin,dmax) class of graphs, and this generalization is used to obtain a strongly polynomial time algorithm that decides membership of a rate-vector where the hosts are distributed within an infinite corridor with fixed cross-section.

In this paper we present a partially asynchronous, fully distributed flow-based access scheme for slotted-time protocols, that guarantees proportional-fairness in ad hoc wireless networks. This problem of providing fairness in wireless networks is considered in the framework of non-linear optimization. We say a medium access control algorithm is proportionally fair with respect to individual end-to-end flows in a network, if the product of the end-to-end flow-success probabilities is maximized.

Fountain codes are designed for erasure channels, and are particularly well suited for broadcast applications from a single source to its one hop receivers. In this context, the problem of designing a rateless code in the network case for on-the-fly recoding is very important, as relaying the data over multiple nodes is fundamentally useful in a network. Clearly, fountain codes are unsuited for on-line recoding (and simply forwarding over subsequent hops is provably suboptimal). Random linear codes are throughput optimal, but they do not enjoy the low complexity that is a prime feature of fountain codes. Can we get the low complexity of say, LT codes, while maintaining on-the-fly recoding and being throughput optimal? This paper proposes a novel solution to the above question. We consider packet level coding on a line network of discrete memoryless erasure channels (with potentially unlimited nodes), and exhibhit a coding scheme with (1) tatelessness (2) logarithmic per-symbol coding complexity (3) throughput optimality (achieves rates equal the min cut capacity) and (4) avoids the delay of having to decode and then re-encode entire block lengths at intermediate nodes.

This paper proposes an approach for providing tolerance against faults that may compromise the functionality of a given controller modeled by a Petri net. The method is based on embedding the given Petri net controller into a larger (redundant) Petri net controller that retains the original functionality and properties, and uses additional places, connections, and tokens to impose invariant conditions that allow the systematic detection and identification of faults via linear parity checks. In particular, this paper considers two types of redundant Petri net controllers: 1) nonseparate redundant Petri net controllers have the same functionality as the given Petri net controller and allow for fault detection and identification, but do not necessarily retain the given controller intact; and 2) separate redundant Petri net controllers are a special case of the nonseparate redundant controllers that retain the given Petri net controller intact but enhance it with additional places to enable fault detection and identification. The work in this paper obtains complete characterizations of both types of redundant controllers along with necessary and sufficient conditions for them to be bisimulation equivalent to the given original Petri net controller. In addition, this paper discusses how each type of redundant controllers can be designed to have desirable fault detection and identification capabilities. When the bisimulation equivalence requirement is not directly enforced, nonseparate redundant controllers can potentially have advantages over separate ones (e.g., they can use fewer connections to detect and identify the same number of faults). An example of a Petri net controller for a production cell and its fault tolerance capabilities using separate and nonseparate embeddings is used to illustrate the approach.

This paper presents a distributed flow-based access scheme for slotted-time protocols that approximates proportional-fairness in ad hoc wireless networks and does not have a significant implementation overhead. We say a medium access control algorithm is proportionally fair with respect to individual end-to-end flows in a network, if the product of the end-to-end flow-success probabilities is maximized. The proposed scheme is implemented using a slotted-time protocol - ST-MAC (Singh, 2004). The authors then compare the performance of the ST-MAC protocol with that of the 802.11-MAC using ns2 simulations of random networks of various sizes. For dense-networks, in terms of packet-delivery-ratios and throughput, the ST-MAC protocol presents an improvement over 802.11-MAC, with comparable end-to-end delay.

Qualitative properties of Petri nets (such as liveness and safeness) are useful in discrete manufacturing applications since they correspond to consistent, deadlock-free control logic. In this paper we introduce the qualitative property of essentially decision free (EDF) places in Petri nets (PNs) to represent the absence of unresolved (nonunique) resource allocation conditions. We show that a previously developed method for PN synthesis of on-line control logic may lead to ambiguous resource allocation conditions which are exhibited in the PN model us non-EDF places. Using the theory of place-invariants, we develop a procedure for identifying non-EDF places in the synthesized logic. The procedure is illustrated for an example of assigning robots to tasks in a flexible assembly cell. For this example, allocation ambiguities are systematically resolved by introducing logical NOT conditions in the PN model.