Total completion time minimization in online hierarchical scheduling of unit-size jobs

This paper investigates an online hierarchical scheduling problem on m parallel identical machines. Our goal is to minimize the total completion time of all jobs. Each job has a unit processing time and a hierarchy. The job with a lower hierarchy can only be processed on the first machine and the job with a higher hierarchy can be processed on any one of m machines. We first show that the lower bound of this problem is at least \(1+\min \{\frac{1}{m}, \max \{\frac{2}{\lceil x\rceil +\frac{x}{\lceil x\rceil }+3}, \frac{2}{\lfloor x\rfloor +\frac{x}{\lfloor x\rfloor }+3}\}\), where \(x=\sqrt{2m+4}\). We then present a greedy algorithm with tight competitive ratio of \(1+\frac{2(m-1)}{m(\sqrt{4m-3}+1)}\). The competitive ratio is obtained in a way of analyzing the structure of the instance in the worst case, which is different from the most common method of competitive analysis. In particular, when \(m=2\), we propose an optimal online algorithm with competitive ratio of \(16\) \(/\) \(13\), which complements the previous result which provided an asymptotically optimal algorithm with competitive ratio of 1.1573 for the case where the number of jobs n is infinite, i.e., \(n\rightarrow \infty \).     

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

Online MapReduce scheduling problem of minimizing the makespan

MapReduce system is a popular big data processing framework, and the performance of it is closely related to the efficiency of the centralized scheduler. In practice, the centralized scheduler often has little information in advance, which means each job may be known only after being released. In this paper, hence, we consider the online MapReduce scheduling problem of minimizing the makespan, where jobs are released over time. Both preemptive and non-preemptive version of the problem are considered. In addition, we assume that reduce tasks cannot be parallelized because they are often complex and hard to be decomposed. For the non-preemptive version, we prove the lower bound is \(\frac{m+m(\Psi (m)-\Psi (k))}{k+m(\Psi (m)-\Psi (k))}\), higher than the basic online machine scheduling problem, where k is the root of the equation \(k=\big \lfloor {\frac{m-k}{1+\Psi (m)-\Psi (k)}+1 }\big \rfloor \) and m is the quantity of machines. Then we devise an \((2-\frac{1}{m})\)-competitive online algorithm called MF-LPT (Map First-Longest Processing Time) based on the LPT. For the preemptive version, we present a 1-competitive algorithm for two machines.     

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.     

Scheduling with interjob communication on parallel processors

Consider a scheduling problem in which a set of tasks needs to be scheduled on m parallel processors. Each task \(T_i\) consists of a set of jobs with interjob communication demands, represented by a weighted, undirected graph \(G_i\). The processors are assumed to be interconnected by a shared communication channel, which can be used by jobs to communicate among each other while being processed in parallel. In each time step, the scheduler assigns jobs to the processors and allows any processed job to use a certain capacity of the channel in order to satisfy (parts of) its communication demands to adjacent jobs processed in the same step. The goal is to find a schedule with minimum length in which the communication demands of all jobs are satisfied. We show that this problem is NP-hard in the strong sense even if the number of processors is constant and the underlying graph is a single path or a forest with arbitrary constant maximum degree. Consequently, we design and analyze approximation algorithms with asymptotic approximation ratio \(\min \{1.8, 1.5 \frac{m}{m-1}\}+1\) if the underlying graph G, the union of the \(G_i\), is a forest. For general graphs it is \(\min \left\{ 1.8, \frac{1.5m}{m-1}\right\} \cdot \left( \text {arb}(G) + \frac{5}{3}\right) \), where \(\text {arb}(G)\) denotes the arboricity of G.     

Semi-online scheduling with known maximum job size on two uniform machines

In this paper, we investigate the semi-online scheduling problem with known maximum job size on two uniform machines with the speed ratio s≥1. The objective is to minimize the makespan. Two algorithms are presented, where the first is optimal for \(1\leq s\leq\sqrt{2}\), and the second is optimal for 1.559≤s≤2 and \(s\ge \frac{3+\sqrt{17}}{2}\). In addition, the improvement on lower bounds is made for \(2.     

Online tradeoff scheduling on a single machine to minimize makespan and maximum lateness

In this paper, we consider the following single machine online tradeoff scheduling problem. A set of n independent jobs arrive online over time. Each job \(J_{j}\) has a release date \(r_{j}\), a processing time \(p_{j}\) and a delivery time \(q_{j}\). The characteristics of a job are unknown until it arrives. The goal is to find a schedule that minimizes the makespan \(C_{\max } = \max _{1 \le j \le n} C_{j}\) and the maximum lateness \(L_{\max } = \max _{1 \le j \le n} L_{j}\), where \(L_{j} = C_{j} + q_{j}\). For the problem, we present a nondominated \(( \rho , 1 + \displaystyle \frac{1}{\rho } )\)-competitive online algorithm for each \(\rho \) with \( 1 \le \rho \le \displaystyle \frac{\sqrt{5} + 1}{2}\).     

Paired-domination number of claw-free odd-regular graphs

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number is the minimum cardinality of a paired-dominating set in the graph, denoted by \(\gamma _{pr}(G)\). Let G be a connected \(\{K_{1,3}, K_{4}-e\}\)-free cubic graph of order n. We show that \(\gamma _{pr}(G)\le \frac{10n+6}{27}\) if G is \(C_{4}\)-free and that \(\gamma _{pr}(G)\le \frac{n}{3}+\frac{n+6}{9(\lceil \frac{3}{4}(g_o+1)\rceil +1)}\) if G is \(\{C_{4}, C_{6}, C_{10}, \ldots , C_{2g_o}\}\)-free for an odd integer \(g_o\ge 3\); the extremal graphs are characterized; we also show that if G is a 2 -connected, \(\gamma _{pr}(G) = \frac{n}{3} \). Furthermore, if G is a connected \((2k+1)\)-regular \(\{K_{1,3}, K_4-e\}\)-free graph of order n, then \(\gamma _{pr}(G)\le \frac{n}{k+1} \), with equality if and only if \(G=L(F)\), where \(F\cong K_{1, 2k+2}\), or k is even and \(F\cong K_{k+1,k+2}\).     

Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem

We consider the problem of scheduling n jobs withrelease dates on m identical parallel machines to minimize the average completion time of the jobs. We prove that the ratio of the average completion time of the optimal nonpreemptive schedule to that of the optimal preemptive schedule is at most 7/3, improving a bound of Shmoys and Wein.     

Semi-online scheduling with combined information on two identical machines in parallel

This paper is concerned with a semi-online scheduling problem with combined information on two identical parallel machines to minimize the makespan, where all the jobs have processing times in the interval \([1,\,t]\)  \((t\ge 1)\) and the jobs arrive in non-increasing order of their processing times. The objective is to minimize the makespan. For \(t\ge 1\), we obtain a lower bound \(\max _{N=1,2,3,\ldots }\left\{ \min \{\frac{4N+3}{4N+2}\,,\frac{Nt+N+1}{2N+1}\}\right\} \) and show that the competitive ratio of the \(LS\) algorithm achieves the lower bound.     

Even factors of graphs

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Favaron and Kouider (J Gr Theory 77:58–67, 2014) showed that if a simple graph G has an even factor, then it has an even factor F with \(|E(F)| \ge \frac{7}{16} (|E(G)| + 1)\). This ratio was improved to \(\frac{4}{7}\) recently by  Chen and Fan (J Comb Theory Ser B 119:237–244, 2016), which is the best possible. In this paper, we take the set of vertices of degree 2 (say \(V_{2}(G)\)) into consideration and further strengthen this lower bound. Our main result is to show that for any simple graph G having an even factor, G has an even factor F with \(|E(F)| \ge \frac{4}{7} (|E(G)| + 1)+\frac{1}{7}|V_{2}(G)|\).     

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.     

Online lazy bureaucrat scheduling with a machine deadline

The lazy bureaucrat scheduling problem was first introduced by Arkin et al. (Inf Comput 184:129–146, 2003). Since then, a number of variants have been addressed. However, very little is known on the online version. In this note we focus on the scenario of online scheduling, in which the jobs arrive over time. The bureaucrat (machine) has a working time interval. Namely, he has a deadline by which all scheduled jobs must be completed. A decision is only based on released jobs without any information on the future. We consider two objective functions of [min-makespan] and [min-time-spent]. Both admit best possible online algorithms with competitive ratio of \(\frac{\sqrt{5}+1}{2}\approx 1.618\).     

Bounding the total domination subdivision number of a graph in terms of its order

The total domination subdivision number \(\mathrm{sd}_{\gamma _{t}}(G)\) of a graph G is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that \(\mathrm{sd}_{\gamma_{t}}(G)\leq \lfloor\frac{2n}{3}\rfloor\) for any simple connected graph G of order n≥3 other than K ₄. We also determine all simple connected graphs G with \(\mathrm{sd}_{\gamma_{t}}(G)=\lfloor\frac{2n}{3}\rfloor\).     

Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling

We consider semi on-line scheduling on two uniform machines. The speed of the slow machine is normalized to 1 while the speed of the fast machine is assumed to be s≥1. Jobs of size J ₁,J ₂,… arrive one at a time, and each J _i (i≥1) has to be assigned to one of the machines before J _i+1 arrives. The assignment cannot be changed later. The processing time of the ith job is J _i on the slow machine and J _i /s on the fast one. The objective is to minimize the makespan. We study both the case where the only information known in advance is the total size ∑_i≥1 J _i of the jobs and the case where the only information known in advance is the optimum makespan. For each of these two cases, we almost completely determine the best possible competitive ratio of semi on-line algorithms compared to the off-line optimum, as a function of s in the range \(1\le s<\frac{1+\sqrt{17}}{4}\approx1.2808\), except for a very short subinterval around s=1.08. We also prove that the best competitive ratio achievable for known optimum is at least as good as the one for known sum, even for any number of uniform machines of any speeds.     

Upper bounds for the total rainbow connection of graphs

A two-agent scheduling problem on parallel machines is considered. Our objective is to minimize the makespan for agent A, subject to an upper bound on the makespan for agent B. When the number of machines, denoted by \(m\), is chosen arbitrarily, we provide an \(O(n)\) algorithm with performance ratio \(2-\frac{1}{m}\), i.e., the makespan for agent A given by the algorithm is no more than \(2-\frac{1}{m}\) times the optimal value, while the makespan for agent B is no more than \(2-\frac{1}{m}\) times the threshold value. This ratio is proved to be tight. Moreover, when \(m=2\), we present an \(O(nlogn)\) algorithm with performance ratio \(\frac{1+\sqrt{17}}{4}\approx 1.28\) which is smaller than \(\frac{3}{2}\). The ratio is weakly tight.     

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.     

Nordhaus–Gaddum type result for the matching number of a graph

For a graph G, \(\alpha '(G)\) is the matching number of G. Let \(k\ge 2\) be an integer, \(K_{n}\) be the complete graph of order n. Assume that \(G_{1}, G_{2}, \ldots , G_{k}\) is a k-decomposition of \(K_{n}\). In this paper, we show that (1)

$$\begin{aligned} \left\lfloor \frac{n}{2}\right\rfloor \le \sum _{i=1}^{k} \alpha '(G_{i})\le k\left\lfloor \frac{n}{2}\right\rfloor . \end{aligned}$$

(2) If each \(G_{i}\) is non-empty for \(i = 1, \ldots , k\), then for \(n\ge 6k\),

$$\begin{aligned} \sum _{i=1}^{k} \alpha '(G_{i})\ge \left\lfloor \frac{n+k-1}{2}\right\rfloor . \end{aligned}$$

(3) If \(G_{i}\) has no isolated vertices for \(i = 1, \ldots , k\), then for \(n\ge 8k\),

$$\begin{aligned} \sum _{i=1}^{k} \alpha '(G_{i})\ge \left\lfloor \frac{n}{2}\right\rfloor +k. \end{aligned}$$

The bounds in (1), (2) and (3) are sharp. (4) When \(k= 2\), we characterize all the extremal graphs which attain the lower bounds in (1), (2) and (3), respectively.

     

Optimal on-line algorithms for one batch machine with grouped processing times

In this paper, we study on-line scheduling problems on a batch machine with the assumption that all jobs have their processing times in [p, (1+φ)p], where p>0 and \(\phi=(\sqrt{5}-1)/2\). Jobs arrive over time. First, we deal with the on-line problem on a bounded batch machine with the objective to minimize makespan. A class of algorithms with competitive ratio \((\sqrt{5}+1)/2\) are given. Then we consider the scheduling on an unbounded batch machine to minimize the time by which all jobs have been delivered, and provide a class of on-line algorithms with competitive ratio \((\sqrt{5}+1)/2\). The two class of algorithms are optimal for the problems studied here.     

Performance ratios of the Karmarkar-Karp differencing method

We consider the multiprocessor scheduling problem in which one must schedule n independent tasks nonpreemptively on m identical, parallel machines, such that the completion time of the last task is minimal. For this well-studied problem the Largest Differencing Method of Karmarkar and Karp outperforms other existing polynomial-time approximation algorithms from an average-case perspective. For m ≥ 3 the worst-case performance of the Largest Differencing Method has remained a challenging open problem. In this paper we show that the worst-case performance ratio is bounded between . For fixed m we establish further refined bounds in terms of n.