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.     

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.     

New results on two-machine flow-shop scheduling with rejection

In this paper, we consider the off-line and on-line two-machine flow-shop scheduling problems with rejection. The objective is to minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs. For the off-line version, Shabtay and Gasper (Comput Oper Res 39:1087–1096, 2012) showed that this problem is NP-hard and then provided a pseudo-polynomial-time algorithm, two 2-approximation algorithms and a fully polynomial-time approximation scheme. We further study some special cases in this paper. We show that this problem is still NP-hard even when all jobs have the same processing time on one of the machines or all jobs have the same rejection penalty. Furthermore, we also showed that this problem can be solved in polynomialtime algorithm when all jobs satisfy the agreeable condition on their processing times and rejection penalties. For the on-line version without rejection, Chen and Woeginger [in: Du DZ, Pardalos PM (eds.) Minimax and Applications, 1995] showed that the competitive ratio of any determined on-line algorithm is at least 2. We further show that the competitive ratio of any determined on-line algorithm is at least 2 even when all jobs have the same processing time on the first machine. Finally, for the on-line version with rejection, we present a class of on-line algorithms with the best-possible competitive ratio 2.     

A bicriteria approach to scheduling a single machine with job rejection and positional penalties

Single machine scheduling problems have been extensively studied in the literature under the assumption that all jobs have to be processed. However, in many practical cases, one may wish to reject the processing of some jobs in the shop, which results in a rejection cost. A solution for a scheduling problem with rejection is given by partitioning the jobs into a set of accepted and a set of rejected jobs, and by scheduling the set of accepted jobs among the machines. The quality of a solution is measured by two criteria: a scheduling criterion, F1, which is dependent on the completion times of the accepted jobs, and the total rejection cost, F2. Problems of scheduling with rejection have been previously studied, but usually within a narrow framework—focusing on one scheduling criterion at a time. This paper provides a robust unified bicriteria analysis of a large set of single machine problems sharing a common property, namely, all problems can be represented by or reduced to a scheduling problem with a scheduling criterion which includes positional penalties. Among these problems are the minimization of the makespan, the sum of completion times, the sum and variation of completion times, and the total earliness plus tardiness costs where the due dates are assignable. Four different problem variations for dealing with the two criteria are studied. The variation of minimizing F1+F2 is shown to be solvable in polynomial time, while all other three variations are shown to be $\mathcal{NP}$ -hard. For those hard problems we provide a pseudo polynomial time algorithm. An FPTAS for obtaining an approximate efficient schedule is provided as well. In addition, we present some interesting special cases which are solvable in polynomial time.     

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}$ .     

Spanning 3-connected index of graphs

For an integer $s>0$ and for $u,v\in V(G)$ with $u\ne v$ , an $(s;u,v)$ -path-system of G is a subgraph H of G consisting of s internally disjoint (u, v)-paths, and such an H is called a spanning $(s;u,v)$ -path system if $V(H)=V(G)$ . The spanning connectivity $\kappa ^{*}(G)$ of graph G is the largest integer s such that for any integer k with $1\le k \le s$ and for any $u,v\in V(G)$ with $u\ne v$ , G has a spanning ( $k;u,v$ )-path-system. Let G be a simple connected graph that is not a path, a cycle or a $K_{1,3}$ . The spanning k-connected index of G, written $s_{k}(G)$ , is the smallest nonnegative integer m such that $L^m(G)$ is spanning k-connected. Let $l(G)=\max \{m:\,G$ has a divalent path of length m that is not both of length 2 and in a $K_{3}$ }, where a divalent path in G is a path whose interval vertices have degree two in G. In this paper, we prove that $s_{3}(G)\le l(G)+6$ . The key proof to this result is that every connected 3-triangular graph is 2-collapsible.     

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.     

On metric dimension of permutation graphs

The metric dimension \(\dim (G)\) of a graph \(G\) is the minimum number of vertices such that every vertex of \(G\) is uniquely determined by its vector of distances to the set of chosen vertices. Let \(G_1\) and \(G_2\) be disjoint copies of a graph \(G\) , and let \(\sigma : V(G_1) \rightarrow V(G_2)\) be a permutation. Then, a permutation graph \(G_{\sigma }=(V, E)\) has the vertex set \(V=V(G_1) \cup V(G_2)\) and the edge set \(E=E(G_1) \cup E(G_2) \cup \{uv \mid v=\sigma (u)\}\) . We show that \(2 \le \dim (G_{\sigma }) \le n-1\) for any connected graph \(G\) of order \(n\) at least \(3\) . We give examples showing that neither is there a function \(f\) such that \(\dim (G) for all pairs \((G,\sigma )\) , nor is there a function \(g\) such that \(g(\dim (G))>\dim (G_{\sigma })\) for all pairs \((G, \sigma )\) . Further, we characterize permutation graphs \(G_{\sigma }\) satisfying \(\dim (G_{\sigma })=n-1\) when \(G\) is a complete \(k\) -partite graph, a cycle, or a path on \(n\) vertices.     

Heterochromatic tree partition number in complete multipartite graphs

The heterochromatic tree partition number of an \(r\) -edge-colored graph \(G,\) denoted by \(t_r(G),\) is the minimum positive integer \(p\) such that whenever the edges of the graph \(G\) are colored with \(r\) colors, the vertices of \(G\) can be covered by at most \(p\) vertex disjoint heterochromatic trees. In this article we determine the upper and lower bounds for the heterochromatic tree partition number \(t_r(K_{n_1,n_2,\ldots ,n_k})\) of an \(r\) -edge-colored complete \(k\) -partite graph \(K_{n_1,n_2,\ldots ,n_k}\) , and the gap between upper and lower bounds is at most one.     

Objective functions with redundant domains

Let $(E,{ \mathcal{A}})$ be a set system consisting of a finite collection ${ \mathcal{A}}$ of subsets of a ground set E, and suppose that we have a function ? which maps ${ \mathcal{A}}$ into some set S. Now removing a subset K from E gives a restriction ${ \mathcal{A}}(\bar{K})$ to those sets of ${ \mathcal{A}}$ disjoint from K, and we have a corresponding restriction $\phi|_{\hspace {.02in}{ \mathcal{A}}(\bar{K})}$ of our function ?. If the removal of K does not affect the image set of ?, that is $\mbox {Im}(\phi|_{\hspace {.02in}{ \mathcal{A}}(\bar{X})})=\mbox {Im}(\phi)$ , then we will say that K is a kernel set of ${ \mathcal{A}}$ with respect to ?. Such sets are potentially useful in optimisation problems defined in terms of ?. We will call the set of all subsets of E that are kernel sets with respect to ? a kernel system and denote it by $\mathrm {Ker}_{\phi}({ \mathcal{A}})$ . Motivated by the optimisation theme, we ask which kernel systems are matroids. For instance, if ${ \mathcal{A}}$ is the collection of forests in a graph G with coloured edges and ? counts how many edges of each colour occurs in a forest then $\mathrm {Ker}_{\phi}({ \mathcal{A}})$ is isomorphic to the disjoint sum of the cocycle matroids of the differently coloured subgraphs; on the other hand, if ${ \mathcal{A}}$ is the power set of a set of positive integers, and ? is the function which takes the values 1 and 0 on subsets according to whether they are sum-free or not, then we show that $\mathrm {Ker}_{\phi}({ \mathcal{A}})$ is essentially never a matroid.     

The partition method for poset-free families

Given a finite poset P, let ${\rm La}(n,P)$ denote the largest size of a family of subsets of an n-set that does not contain P as a (weak) subposet. We employ a combinatorial method, using partitions of the collection of all full chains of subsets of the n-set, to give simpler new proofs of the known asymptotic behavior of ${\rm La}(n,P)$ , as n→∞, when P is the r-fork $\mathcal {V}_{r}$ , the four-element N poset $\mathcal {N}$ , and the four-element butterfly-poset $\mathcal {B}$ .     

Graphs with small balanced decomposition numbers

A balanced coloring of a graph \(G\) is an ordered pair \((R,B)\) of disjoint subsets \(R,B \subseteq V(G)\) with \(|R|=|B|\) . The balanced decomposition number  \(f(G)\) of a connected graph \(G\) is the minimum integer \(f\) such that for any balanced coloring \((R,B)\) of \(G\) there is a partition \(\mathcal{P}\) of \(V(G)\) such that \(S\) induces a connected subgraph with \(|S| \le f\) and \(|S \cap R| = |S \cap B|\) for \(S \in \mathcal{P}\) . This paper gives a short proof for the result by Fujita and Liu (2010) that a graph \(G\) of \(n\) vertices has \(f(G)=3\) if and only if \(G\) is \(\lfloor \frac{n}{2} \rfloor \) -connected but is not a complete graph.     

Mobile facility location: combinatorial filtering via weighted occupancy

An instance of the mobile facility location problem consists of a complete directed graph \(G = (V, E)\) , in which each arc \((u, v) \in E\) is associated with a numerical attribute \(\mathcal M (u,v)\) , representing the cost of moving any object from \(u\) to \(v\) . An additional ingredient of the input is a collection of servers \(S = \{ s_1, \ldots , s_k \}\) and a set of clients \(C = \{ c_1, \ldots , c_\ell \}\) , which are located at nodes of the underlying graph. With this setting in mind, a movement scheme is a function \(\psi : S \rightarrow V\) that relocates each server \(s_i\) to a new position, \(\psi ( s_i )\) . We refer to \(\mathcal M ( s_i, \psi ( s_i ) )\) as the relocation cost of \(s_i\) , and to \(\min _{i \in [k]} \mathcal M (c_j, \psi ( s_i ) )\) , the cost of assigning client \(c_j\) to the nearest final server location, as the service cost of \(c_j\) . The objective is to compute a movement scheme that minimizes the sum of relocation and service costs. In this paper, we resolve an open question posed by Demaine et al. (SODA ’07) by characterizing the approximability of mobile facility location through LP-based methods. We also develop a more efficient algorithm, which is based on a combinatorial filtering approach. The latter technique is of independent interest, as it may be applicable in other settings as well. In this context, we introduce a weighted version of the occupancy problem, for which we establish interesting tail bounds, not before demonstrating that existing bounds cannot be extended.     

Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees

We consider two related problems: the multiple-depot vehicle routing problem (MDVRP) and the Multiple traveling salesman problem (mTSP). In both of them, given is the complete graph on n vertices \(G = (V,E)\) with nonnegative edge lengths that form a metric on V. Also given is a positive integer k. In typical applications, V represents locations of customers and k represents the number of available vehicles. In MDVPR, we are also given a set of k depots \(\{O_1,\ldots ,O_k\} \subseteq V\) , and the goal is to find a minimum-length cycle cover of G of size k, that is, a collection of k (possibly empty) cycles such that each \(v \in V\) is in exactly one cycle, and each cycle in the cover contains exactly one depot. In mTSP, no depots are given, so the goal is to find (any) minimum-length cycle cover of G of size k. We present local search algorithms for both problems, and we prove that their approximation ratio is 2.     

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.     

Realizations of the game domination number

Domination game is a game on a finite graph which includes two players. First player, Dominator, tries to dominate a graph in as few moves as possible; meanwhile the second player, Staller, tries to hold him back and delay the end of the game as long as she can. In each move at least one additional vertex has to be dominated. The number of all moves in the game in which Dominator makes the first move and both players play optimally is called the game domination number and is denoted by \(\gamma _g\) . The total number of moves in a Staller-start game is denoted by \(\gamma _g^{\prime }\) . It is known that \(|\gamma _g(G)-\gamma _g^{\prime }(G)|\le 1\) for any graph \(G\) . Graph \(G\) realizes a pair \((k,l)\) if \(\gamma _g(G)=k\) and \(\gamma _g^{\prime }(G)=l\) . It is shown that pairs \((2k,2k-1)\) for all \(k\ge 2\) can be realized by a family of 2-connected graphs. We also present 2-connected classes which realize pairs \((k,k)\) and \((k,k+1)\) . Exact game domination number for combs and 1-connected realization of the pair \((2k+1,2k)\) are also given.     

F_{3}-domination problem of graphs

Given a graph \(G\) and a set \(S\subseteq V(G),\) a vertex \(v\) is said to be \(F_{3}\) -dominated by a vertex \(w\) in \(S\) if either \(v=w,\) or \(v\notin S\) and there exists a vertex \(u\) in \(V(G)-S\) such that \(P:wuv\) is a path in \(G\) . A set \(S\subseteq V(G)\) is an \(F_{3}\) -dominating set of \(G\) if every vertex \(v\) is \(F_{3}\) -dominated by a vertex \(w\) in \(S.\) The \(F_{3}\) -domination number of \(G\) , denoted by \(\gamma _{F_{3}}(G)\) , is the minimum cardinality of an \(F_{3}\) -dominating set of \(G\) . In this paper, we study the \(F_{3}\) -domination of Cartesian product of graphs, and give formulas to compute the \(F_{3}\) -domination number of \(P_{m}\times P_{n}\) and \(P_{m}\times C_{n}\) for special \(m,n.\)      

Optimal strategies for the one-round discrete Voronoi game on a line

The one-round discrete Voronoi game, with respect to a n-point user set  $\mathcal {U}$ , consists of two players Player 1 (P1) and Player 2 (P2). At first, P1 chooses a set $\mathcal{F}_{1}$ of m facilities following which P2 chooses another set $\mathcal{F}_{2}$ of m facilities, disjoint from  $\mathcal{F}_{1}$ , where m(=O(1)) is a positive constant. The payoff of P2 is defined as the cardinality of the set of points in $\mathcal{U}$ which are closer to a facility in $\mathcal{F}_{2}$ than to every facility in $\mathcal{F}_{1}$ , and the payoff of P1 is the difference between the number of users in $\mathcal{U}$ and the payoff of P2. The objective of both the players in the game is to maximize their respective payoffs. In this paper, we address the case where the points in $\mathcal{U}$ are located along a line. We show that if the sorted order of the points in $\mathcal{U}$ along the line is known, then the optimal strategy of P2, given any placement of facilities by P1, can be computed in O(n) time. We then prove that for m≥2 the optimal strategy of P1 in the one-round discrete Voronoi game, with the users on a line, can be computed in $O(n^{m-\lambda_{m}})$ time, where 0<λ _m <1, is a constant depending only on m.     

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 \) .     

On colour-blind distinguishing colour pallets in regular graphs

Consider a graph \(G=(V,E)\) and a colouring of its edges with \(k\) colours. Then every vertex \(v\in V\) is associated with a ‘pallet’ of incident colours together with their frequencies, which sum up to the degree of \(v\) . We say that two vertices have distinct pallets if they differ in frequency of at least one colour. This is always the case if these vertices have distinct degrees. We consider an apparently the worse case, when \(G\) is regular. Suppose further that this coloured graph is being examined by a person who cannot name any given colour, but distinguishes one from another. Could we colour the edges of \(G\) so that a person suffering from such colour-blindness is certain that colour pallets of every two adjacent vertices are distinct? Using the Lopsided Lovász Local Lemma, we prove that it is possible using 15 colours for every \(d\) -regular graph with \(d\ge 960\) .