On rescheduling due to machine disruption while to minimize the total weighted completion time

We investigate a single machine rescheduling problem that arises from an unexpected machine unavailability, after the given set of jobs has already been scheduled to minimize the total weighted completion time. Such a disruption is represented as an unavailable time interval and is revealed to the production planner before any job is processed; the production planner wishes to reschedule the jobs to minimize the alteration to the originally planned schedule, which is measured as the maximum time deviation between the original and the new schedules for all the jobs. The objective function in this rescheduling problem is to minimize the sum of the total weighted completion time and the weighted maximum time deviation, under the constraint that the maximum time deviation is bounded above by a given value. That is, the maximum time deviation is taken both as a constraint and as part of the objective function. We present a pseudo-polynomial time exact algorithm and a fully polynomial time approximation scheme, the latter of which is the best possible given that the general problem is NP-hard.

Comments: 17 pages

Similar Publications

In this work, we provide a general framework for adding a linearizable iterator to data structures with set operations. We propose a condition on these set operations, called locality, so that any data structure implemented from local atomic operations can be augmented with a linearizable iterator as described by our framework. We then apply the iterator framework to various data structures, prove locality of their operations, and demonstrate that the iterator framework does not significantly affect the performance of concurrent operations. Read More

In the k-partition problem (k-PP), one is given an edge-weighted undirected graph, and one must partition the node set into at most k subsets, in order to minimise (or maximise) the total weight of the edges that have their end-nodes in the same cluster. Various hierarchical variants of this problem have been studied in the context of data mining. We consider a 'two-level' variant that arises in mobile wireless communications. Read More

We introduce a technique to turn dynamic programming tasks on labeled directed acyclic graphs (labeled DAGs) closer to their sequence analogies. We demonstrate the technique on three problems: longest increasing subsequence, longest common subsequence, and co-linear chaining extended to labeled DAGs. For the former we obtain an algorithm with running time $O(|E| k \log |V|+ |V| k \log^2 |V|)$, where $V$ and $E$ are the set of vertices and edges, respectively, and $k$ is the minimum size of a path cover of $V$. Read More

Integer Linear Programming is a famous NP-complete problem. Lenstra showed that in the case of small dimension, it can be solved in polynomial time. This algorithm became a ubiquitous tool, especially in the design of parameterized algorithms for NP-complete problems, where we wish to isolate the hardness of an instance to some parameter. Read More

Given a string $T$, it is known that its suffix tree can be represented using the compact directed acyclic word graph (CDAWG) with $e_T$ arcs, taking overall $O(e_T+e_{{\overline{T}}})$ words of space, where ${\overline{T}}$ is the reverse of $T$, and supporting some key operations in time between $O(1)$ and $O(\log{\log{n}})$ in the worst case. This representation is especially appealing for highly repetitive strings, like collections of similar genomes or of version-controlled documents, in which $e_T$ grows sublinearly in the length of $T$ in practice. In this paper we augment such representation, supporting a number of additional queries in worst-case time between $O(1)$ and $O(\log{n})$ in the RAM model, without increasing space complexity asymptotically. Read More

We propose an iterated local search based on several classes of local and large neighborhoods for the bin packing problem with conflicts. This problem, which combines the characteristics of both bin packing and vertex coloring, arises in various application contexts such as logistics and transportation, timetabling, and resource allocation for cloud computing. We introduce $O(1)$ evaluation procedures for classical local-search moves, polynomial variants of ejection chains and assignment neighborhoods, an adaptive set covering-based neighborhood, and finally a controlled use of 0-cost moves to further diversify the search. Read More

In this paper we initiate the study of property testing in simultaneous and non-simultaneous multi-party communication complexity, focusing on testing triangle-freeness in graphs. We consider the $\textit{coordinator}$ model, where we have $k$ players receiving private inputs, and a coordinator who receives no input; the coordinator can communicate with all the players, but the players cannot communicate with each other. In this model, we ask: if an input graph is divided between the players, with each player receiving some of the edges, how many bits do the players and the coordinator need to exchange to determine if the graph is triangle-free, or $\textit{far}$ from triangle-free? For general communication protocols, we show that $\tilde{O}(k(nd)^{1/4}+k^2)$ bits are sufficient to test triangle-freeness in graphs of size $n$ with average degree $d$ (the degree need not be known in advance). Read More

We develop a coalgebraic generalization of the classical Paige-Tarjan algorithm for efficient bisimilarity checking. Coalgebraic generality implies that our algorithm applies to systems beyond the standard relational setup, in particular various flavours of weighted systems. The specific requirements of the algorithm force rather strong assumptions on the coalgebraic type functors, but by using modularity principles in multi-sorted coalgebra and generalizing our methods beyond the category of sets, we nevertheless arrive at covering not just the known examples (transition systems and Markov chains) but also systems with mixed transition types, such as Segala-style probabilistic automata. Read More

We analyze the caching overhead incurred by a class of multithreaded algorithms when scheduled by an arbitrary scheduler. We obtain bounds that match or improve upon the well-known $O(Q+S \cdot (M/B))$ caching cost for the randomized work stealing (RWS) scheduler, where $S$ is the number of steals, $Q$ is the sequential caching cost, and $M$ and $B$ are the cache size and block (or cache line) size respectively. Read More

In a vertex-colored graph, an edge is happy if its endpoints have the same color. Similarly, a vertex is happy if all its incident edges are happy. Motivated by the computation of homophily in social networks, we consider the algorithmic aspects of the following Maximum Happy Edges (k-MHE) problem: given a partially k-colored graph G, find an extended full k-coloring of G maximizing the number of happy edges. Read More