Optimal job insertion in the no-wait job shop

The no-wait job shop (NWJS) considered here is a version of the job shop scheduling problem where, for any two operations of a job, a fixed time lag between their starting times is given. Also, sequence-dependent set-up times between consecutive operations on a machine can be present. The NWJS problem consists in finding a schedule that minimizes the makespan. We address here the so-called optimal job insertion problem (OJI) in the NWJS. While the OJI is NP-hard in the classical job shop, it was shown by Gröflin & Klinkert to be solvable in polynomial time in the NWJS. We present a highly efficient algorithm with running time $\mathcal {O}(n^{2}\cdot\max\{n,m\})$ for this problem. The algorithm is based on a compact formulation of the NWJS problem and a characterization of all feasible insertions as the stable sets (of prescribed cardinality) in a derived comparability graph. As an application of our algorithm, we propose a heuristic for the NWJS problem based on optimal job insertion and present numerical results that compare favorably with current benchmarks.     

Online scheduling with rejection and reordering: exact algorithms for unit size jobs

We study an online scheduling problem with rejection on \(m\ge 2\) identical machines, in which we deal with unit size jobs. Each arriving job has a rejection value (a rejection cost or penalty for minimization problems, and a rejection profit for maximization problems) associated with it. A buffer of size \(K\) is available to store \(K\) jobs. A job which is not stored in the buffer must be either assigned to a machine or rejected. Upon the arrival of a new job, the job can be stored in the buffer if there is a free slot (possibly created by evicting other jobs and assigning or rejecting every evicted job). At termination, the buffer must be emptied. We study four variants of the problem, as follows. We study the makespan minimization problem, where the goal is to minimize the sum of the makespan and the penalty of rejected jobs, and the \(\ell _p\) norm minimization problem, where the goal is to minimize the sum of the \(\ell _p\) norm of the vector of machine completion times and the penalty of rejected jobs. We also study two maximization problems, where the goal in the first version is to maximize the sum of the minimum machine load (the cover value of the machines) and the total rejection profit, and in the second version the goal is to maximize a function of the machine completion times (which measures the balance of machine loads) and the total rejection profit. We show that an optimal solution (an exact solution for the offline problem) can always be obtained in this environment, and determine the required buffer size. Specifically, for all four variants we present optimal algorithms with \(K=m-1\) and prove that in each case, using a buffer of size at most \(m-2\) does not allow the design of an optimal algorithm, which makes our algorithms optimal in this respect as well. The lower bounds hold even for the special case where the rejection value is equal for all input jobs.     

On the generalized multiway cut in trees problem

Given a tree $T = (V, E)$ with $n$ vertices and a collection of terminal sets $D = \{S_1, S_2, \ldots , S_c\}$ , where each $S_i$ is a subset of $V$ and $c$ is a constant, the generalized multiway cut in trees problem (GMWC(T)) asks to find a minimum size edge subset $E^{\prime } \subseteq E$ such that its removal from the tree separates all terminals in $S_i$ from each other for each terminal set $S_i$ . The GMWC(T) problem is a natural generalization of the classical multiway cut in trees problem, and has an implicit relation to the Densest $k$ -Subgraph problem. In this paper, we show that the GMWC(T) problem is fixed-parameter tractable by giving an $O(n^2 + 2^k)$ time algorithm, where $k$ is the size of an optimal solution, and the GMWC(T) problem is polynomial time solvable when the problem is restricted in paths.We also discuss some heuristics for the GMWC(T) problem     

Two-stage proportionate flexible flow shop to minimize the makespan

We consider a two-stage flexible flow shop problem with a single machine at one stage and m identical machines at the other stage, where the processing times of each job at both stages are identical. The objective is to minimize the makespan. We describe some optimality conditions and show that the problem is NP-hard when m is fixed. Finally, we present an approximation algorithm that has a worst-case performance ratio of $\frac{5}{4}$ for m=2 and $\frac{\sqrt{1+m^{2}}+1+m}{2m}$ for m≥3.     

Scheduling with release times and rejection on two parallel machines

In this paper we study scheduling with release times and job rejection on two parallel machines. In our scheduling model each job is either accepted and then processed by one of the two machines at or after its release time, or it is rejected and then a rejection penalty is paid. The objective is to minimize the makespan of the accepted job plus the total penalty of all rejected jobs. The scheduling problem is NP-hard in the ordinary sense. In this paper, we develop a \(1.5+\epsilon \)-approximation algorithm for the problem, where \(\epsilon \) is any given small positive constant.     

Minimum diameter cost-constrained Steiner trees

Given an edge-weighted undirected graph $G=(V,E,c,w)$ where each edge $e\in E$ has a cost $c(e)\ge 0$ and another weight $w(e)\ge 0$ , a set $S\subseteq V$ of terminals and a given constant $\mathrm{C}_0\ge 0$ , the aim is to find a minimum diameter Steiner tree whose all terminals appear as leaves and the cost of tree is bounded by $\mathrm{C}_0$ . The diameter of a tree refers to the maximum weight of the path connecting two different leaves in the tree. This problem is called the minimum diameter cost-constrained Steiner tree problem, which is NP-hard even when the topology of the Steiner tree is fixed. In this paper, we deal with the fixed-topology restricted version. We prove the restricted version to be polynomially solvable when the topology is not part of the input and propose a weakly fully polynomial time approximation scheme (weakly FPTAS) when the topology is part of the input, which can find a $(1+\epsilon )$ –approximation of the restricted version problem for any $\epsilon >0$ with a specific characteristic.     

Semi-online scheduling for jobs with release times

In this paper we consider three semi-online scheduling problems for jobs with release times on m identical parallel machines. The worst case performance ratios of the LS algorithm are analyzed. The objective function is to minimize the maximum completion time of all machines, i.e. the makespan. If the job list has a non-decreasing release times, then $2-\frac{1}{m}$ is the tight bound of the worst case performance ratio of the LS algorithm. If the job list has non-increasing processing times, we show that $2-\frac{1}{2m}$ is an upper bound of the worst case performance ratio of the LS algorithm. Furthermore if the job list has non-decreasing release times and the job list has non-increasing processing times we prove that the LS algorithm has worst case performance ratio not greater than $\frac{3}{2} -\frac{1}{2m}$ .     

Minimizing the number of tardy jobs in two-machine settings with common due date

We consider two-machine scheduling problems with job selection. We analyze first the two-machine open shop problem and provide a best possible linear time algorithm. Then, a best possible linear time algorithm is derived for the job selection problem on two unrelated parallel machines. We also show that an exact approach can be derived for both problems with complexity \(O(p(n) \times \sqrt{2}^n)\), p being a polynomial function of n.     

Recognition of overlap graphs

Overlap graphs occur in computational biology and computer science, and have applications in genome sequencing, string compression, and machine scheduling. Given two strings \(s_{i}\) and \(s_{j}\) , their overlap string is defined as the longest string \(v\) such that \(s_{i} = uv\) and \(s_{j} = vw\) , for some non empty strings \(u,w\) , and its length is called the overlap between these two strings. A weighted directed graph is an overlap graph if there exists a set of strings with one-to-one correspondence to the vertices of the graph, such that each arc weight in the graph equals the overlap between the corresponding strings. In this paper, we characterize the class of overlap graphs, and we present a polynomial time recognition algorithm as a direct consequence. Given a weighted directed graph \(G\) , the algorithm constructs a set of strings that has \(G\) as its overlap graph, or decides that this is not possible.     

The cost of selfishness for maximizing the minimum load on uniformly related machines

Consider the following scheduling game. A set of jobs, each controlled by a selfish agent, are to be assigned to m uniformly related machines. The cost of a job is defined as the total load of the machine that its job is assigned to. A job is interested in minimizing its cost, while the social objective is maximizing the minimum load (the value of the cover) over the machines. This goal is different from the regular makespan minimization goal, which was extensively studied in a game theoretic context. We study the price of anarchy (poa) and the price of stability (pos) for uniformly related machines. The results are expressed in terms of s, which is the maximum speed ratio between any two machines. For uniformly related machines, we prove that the pos is unbounded for s>2, and the poa is unbounded for s≥2. For the remaining cases we show that while the poa grows to infinity as s tends to 2, the pos is at most 2 for any s≤2.     

Semi-online scheduling on two identical machines with rejection

In this paper we consider two semi-online scheduling problems with rejection on two identical machines. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive one by one and can be either rejected by paying a certain penalty or assigned to some machine. No preemption is allowed. The objective is to minimize the sum of the makespan of schedule, which is yielded by all accepted jobs and the total penalties of all rejected ones. In the first problem one can reassign several scheduled jobs in rejection tache, in the second a buffer with length k is available in rejection tache. Two optimal algorithms both with competitive ratio $\frac{3}{2}$ are presented.     

Online bottleneck matching

We consider the online bottleneck matching problem, where $k$ server-vertices lie in a metric space and $k$ request-vertices that arrive over time each must immediately be permanently assigned to a server-vertex. The goal is to minimize the maximum distance between any request and its server. Because no algorithm can have a competitive ratio better than $O(k)$ for this problem, we use resource augmentation analysis to examine the performance of three algorithms: the naive Greedy algorithm, Permutation, and Balance. We show that while the competitive ratio of Greedy improves from exponential (when each server-vertex has one server) to linear (when each server-vertex has two servers), the competitive ratio of Permutation remains linear when an extra server is introduced at each server-vertex. The competitive ratio of Balance is also linear with an extra server at each server-vertex, even though it has been shown that an extra server makes it constant-competitive for the min-weight matching problem.     

Computing an effective decision making group of a society using social network analysis

Recent years have witnessed how much a decision making group can be dysfunctional due to the extreme hyperpartisanship. While partisanship is crucial for the representatives to pursue the wishes of those whom they represent for, such an extremism results in a severe gridlock in the decision making progress, and makes themselves highly inefficient. It is known that such a problem can be mitigated by having negotiators in the group. This paper investigates the potential of social network analysis techniques to choose an effective leadership group of a society such that it suffers less from the extreme hyperpartisanship. We establish three essential requirements for an effective representative group, namely Influenceability, Partisanship, and Bipartisanship. Then, we formulate the problem of finding a minimum size representative group satisfying the three requirements as the minimum connected \(k\) -core dominating set problem (MC \(k\) CDSP), and show its NP-hardness. We introduce an extension of MC \(k\) CDSP, namely MC \(k\) CDSP-C, which assumes the society has a number of sub-communities and requires at least one representative from each sub-community should be in the leadership. We also propose an approximation algorithm for a subclass of MC \(k\) CDSP with \(k=2\) , and show an \(\alpha \) -approximation algorithm of MC \(k\) CDSP can be used to obtain an \(\alpha \) -approximation algorithm of MC \(k\) CDSP-SC.     

2-Distance vertex-distinguishing index of subcubic graphs

This paper addresses the performance of scheduling algorithms for a two-stage no-wait hybrid flowshop environment with inter-stage flexibility, where there exist several parallel machines at each stage. Each job, composed of two operations, must be processed from start to completion without any interruption either on or between the two stages. For each job, the total processing time of its two operations is fixed, and the stage-1 operation is divided into two sub-parts: an obligatory part and an optional part (which is to be determined by a solution), with a constraint that no optional part of a job can be processed in parallel with an idleness of any stage-2 machine. The objective is to minimize the makespan. We prove that even for the special case with only one machine at each stage, this problem is strongly NP-hard. For the case with one machine at stage 1 and m machines at stage 2, we propose two polynomial time approximation algorithms with worst case ratio of \(3-\frac{2}{m+1}\) and \(2-\frac{1}{m+1}\), respectively. For the case with m machines at stage 1 and one machine at stage 2, we propose a polynomial time approximation algorithm with worst case ratio of 2. We also prove that all the worst case ratios are tight.     

Algorithms for local similarity between forests

An ordered labelled tree is a tree where the left-to-right order among siblings is significant. Ordered labelled forests are sequences of ordered labelled trees. Given two ordered labelled forests $F$ and $G$ , the local forest similarity is to find two sub-forests $F^{\prime }$ and $G^{\prime }$ of $F$ and $G$ respectively such that they are the most similar over all possible $F^{\prime }$ and $G^{\prime }$ . In this paper, we present efficient algorithms for the local forest similarity problem for two types of sub-forests: sibling subforests and closed subforests. Our algorithms can be used to locate the structurally similar regions in RNA secondary structures since RNA molecules’ secondary structures could be represented as ordered labelled forests.     

An optimal online algorithm for the parallel-batch scheduling with job processing time compatibilities

We consider the online (over time) scheduling on a single unbounded parallel-batch machine with job processing time compatibilities to minimize makespan. In the problem, a constant \(\alpha >0\) is given in advance. Each job \(J_{j}\) has a normal processing time \(p_j\). Two jobs \(J_i\) and \(J_j\) are compatible if \(\max \{p_i, p_j\} \le (1+\alpha )\cdot \min \{p_i, p_j\}\). In the problem, mutually compatible jobs can form a batch being processed on the machine. The processing time of a batch is equal to the maximum normal processing time of the jobs in this batch. For this problem, we provide an optimal online algorithm with a competitive ratio of \(1+\beta _\alpha \), where \(\beta _\alpha \) is the positive root of the equation \((1+\alpha )x^{2}+\alpha x=1+\alpha \).     

Radiation hybrid map construction problem parameterized

In this paper, we study the Radiation hybrid map construction ( $\mathsf{{RHMC} }$ ) problem which is about reconstructing a genome from a set of gene clusters. The problem is known to be $\mathsf{{NP} }$ -complete even when all gene clusters are of size two and the corresponding problem ( $\mathsf{{RHMC}_2 }$ ) admits efficient constant-factor approximation algorithms. In this paper, for the first time, we consider the more general case when the gene clusters can have size either two or three ( $\mathsf{{RHMC}_3 }$ ). Let ${p\text{- }\mathsf {RHMC} }$ be a parameterized version of $\mathsf{{RHMC} }$ where the parameter is the size of solution. We present a linear kernel for ${p\text{- }\mathsf {RHMC}_3 }$ of size $22k$ that when combined with a bounded search-tree algorithm, gives an FPT algorithm running in $O(6^kk+n)$ time. For ${p\text{- }\mathsf {RHMC}_3 }$ we present a bounded search tree algorithm which runs in $O^*(2.45^k)$ time, greatly improving the previous bound using weak kernels.     

Minimum number of disjoint linear forests covering a planar graph

Graph coloring has interesting real-life applications in optimization, computer science and network design, such as file transferring in a computer network, computation of Hessians matrix and so on. In this paper, we consider one important coloring, linear arboricity, which is an improper edge coloring. Moreover, we study linear arboricity on planar graphs with maximum degree \(\varDelta \ge 7\) . We have proved that the linear arboricity of \(G\) is \(\lceil \frac{\varDelta }{2}\rceil \) , if for each vertex \(v\in V(G)\) , there are two integers \(i_v,j_v\in \{3,4,5,6,7,8\}\) such that any two cycles of length \(i_v\) and \(j_v\) , which contain \(v\) , are not adjacent. Clearly, if \(i_v=i, j_v=j\) for each vertex \(v\in V(G)\) , then we can easily get one corollary: for two fixed integers \(i,j\in \{3,4,5,6,7,8\}\) , if there is no adjacent cycles with length \(i\) and \(j\) in \(G\) , then the linear arboricity of \(G\) is \(\lceil \frac{\varDelta }{2}\rceil \) .     

Popularity at minimum cost

We consider an extension of the popular matching problem in this paper. The input to the popular matching problem is a bipartite graph $G = (\mathcal{A}\cup\mathcal{B},E)$ , where $\mathcal{A}$ is a set of people, $\mathcal{B}$ is a set of items, and each person $a \in\mathcal{A}$ ranks a subset of items in order of preference, with ties allowed. The popular matching problem seeks to compute a matching M ^? between people and items such that there is no matching M where more people are happier with M than with M ^?. Such a matching M ^? is called a popular matching. However, there are simple instances where no popular matching exists. Here we consider the following natural extension to the above problem: associated with each item $b \in\mathcal{B}$ is a non-negative price cost(b), that is, for any item b, new copies of b can be added to the input graph by paying an amount of cost(b) per copy. When G does not admit a popular matching, the problem is to “augment” G at minimum cost such that the new graph admits a popular matching. We show that this problem is NP-hard; in fact, it is NP-hard to approximate it within a factor of $\sqrt{n_{1}}/2$ , where n ₁ is the number of people. This problem has a simple polynomial time algorithm when each person has a preference list of length at most 2. However, if we consider the problem of constructing a graph at minimum cost that admits a popular matching that matches all people, then even with preference lists of length 2, the problem becomes NP-hard. On the other hand, when the number of copies of each item is fixed, we show that the problem of computing a minimum cost popular matching or deciding that no popular matching exists can be solved in O(mn ₁) time, where m is the number of edges.     

Colorability of mixed hypergraphs and their chromatic inversions

We solve a long-standing open problem concerning a discrete mathematical model, which has various applications in computer science and several other fields, including frequency assignment and many other problems on resource allocation. A mixed hypergraph $\mathcal H $ is a triple $(X,\mathcal C ,\mathcal D )$ , where $X$ is the set of vertices, and $\mathcal C $ and $\mathcal D $ are two set systems over $X$ , the families of so-called C-edges and D-edges, respectively. A vertex coloring of a mixed hypergraph $\mathcal H $ is proper if every C-edge has two vertices with a common color and every D-edge has two vertices with different colors. A mixed hypergraph is colorable if it has at least one proper coloring; otherwise it is uncolorable. The chromatic inversion of a mixed hypergraph $\mathcal H =(X,\mathcal C ,\mathcal D )$ is defined as $\mathcal H ^c=(X,\mathcal D ,\mathcal C )$ . Since 1995, it was an open problem wether there is a correlation between the colorability properties of a hypergraph and its chromatic inversion. In this paper we answer this question in the negative, proving that there exists no polynomial-time algorithm (provided that $P \ne NP$ ) to decide whether both $\mathcal H $ and $\mathcal H ^c$ are colorable, or both are uncolorable. This theorem holds already for the restricted class of 3-uniform mixed hypergraphs (i.e., where every edge has exactly three vertices). The proof is based on a new polynomial-time algorithm for coloring a special subclass of 3-uniform mixed hypergraphs. Implementation in C++ programming language has been tested. Further related decision problems are investigated, too.