Two-agent scheduling of time-dependent jobs

We consider the problem of scheduling deteriorating jobs or shortening jobs with two agents A and B. We are interested in generating all Pareto-optimal schedules for the two criteria: (1) the total completion time of the jobs in A and the maximum cost of the jobs in B, and (2) the maximum cost of the jobs in A and the maximum cost of the jobs in B. We show that all Pareto-optimal schedules for both problems can be generated in polynomial time, whether the jobs are deteriorating or shortening.     

A coordination mechanism for a scheduling game with parallel-batching machines

In this paper we consider the scheduling problem with parallel-batching machines from a game theoretic perspective. There are m parallel-batching machines each of which can handle up to b jobs simultaneously as a batch. The processing time of a batch is the time required for processing the longest job in the batch, and all the jobs in a batch start and complete at the same time. There are n jobs. Each job is owned by a rational and selfish agent and its individual cost is the completion time of its job. The social cost is the largest completion time over all jobs, the makespan. We design a coordination mechanism for the scheduling game problem. We discuss the existence of pure Nash Equilibria and offer upper and lower bounds on the price of anarchy of the coordination mechanism. We show that the mechanism has a price of anarchy no more than \(2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}\).     

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.     

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.     

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.     

Incremental Facility Location Problem and Its Competitive Algorithms

We consider the incremental version of the k-Facility Location Problem, which is a common generalization of the facility location and the k-median problems. The objective is to produce an incremental sequence of facility sets F ₁?F ₂?????F _n , where each F _k contains at most k facilities. An incremental facility sequence or an algorithm producing such a sequence is called c -competitive if the cost of each F _k is at most c times the optimum cost of corresponding k-facility location problem, where c is called competitive ratio. In this paper we present two competitive algorithms for this problem. The first algorithm produces competitive ratio 8α, where α is the approximation ratio of k-facility location problem. By recently result (Zhang, Theor. Comput. Sci. 384:126–135, 2007), we obtain the competitive ratio \(16+8\sqrt{3}+\epsilon\). The second algorithm has the competitive ratio Δ+1, where Δ is the ratio between the maximum and minimum nonzero interpoint distances. The latter result has its self interest, specially for the small metric space with Δ≤8α?1.     

On the minimum routing cost clustered tree problem

For an edge-weighted graph \(G=(V,E,w)\), in which the vertices are partitioned into k clusters \(\mathcal {R}=\{R_1,R_2,\ldots ,R_k\}\), a spanning tree T of G is a clustered spanning tree if T can be cut into k subtrees by removing \(k-1\) edges such that each subtree is a spanning tree for one cluster. In this paper, we show the inapproximability of finding a clustered spanning tree with minimum routing cost, where the routing cost is the total distance summed over all pairs of vertices. We present a 2-approximation for the case that the input is a complete weighted graph whose edge weights obey the triangle inequality. We also study a variant in which the objective function is the total distance summed over all pairs of vertices of different clusters. We show that the problem is polynomial-time solvable when the number of clusters k is 2 and NP-hard for \(k=3\). Finally, we propose a polynomial-time 2-approximation algorithm for the case of three clusters.     

Approximating capacitated tree-routings in networks

Let G=(V,E) be a connected graph such that each edge e∈E is weighted by a nonnegative real w(e). Let s be a vertex designated as a sink, M?V be a set of terminals with a demand function q:M→R ⁺, κ>0 be a routing capacity, and λ≥1 be an integer edge capacity. The capacitated tree-routing problem (CTR) asks to find a partition ?={Z ₁,Z ₂,…,Z _? } of M and a set \({\mathcal{T}}=\{T_{1},T_{2},\ldots,T_{\ell}\}\) of trees of G such that each T _i contains Z _i ∪{s} and satisfies \(\sum_{v\in Z_{i}}q(v)\leq \kappa\). A single copy of an edge e∈E can be shared by at most λ trees in \({\mathcal{T}}\); any integer number of copies of e are allowed to be installed, where the cost of installing a copy of e is w(e). The objective is to find a solution \(({\mathcal{M}},{\mathcal{T}})\) that minimizes the total installing cost. In this paper, we propose a (2+ρ _ST )-approximation algorithm to CTR, where ρ _ST is any approximation ratio achievable for the Steiner tree problem.     

An optimal semi-online algorithm for 2-machine scheduling with an availability constraint

This paper considers a problem of semi-online scheduling jobs on two identical parallel machines with objective to minimize the makespan. We assume there is an unavailable period [B,F] on one machine and the largest job processing time P _max? is known in advance. After comparing B with P _max? we consider three cases, and we show a lower bound of the problem are 3/2, 4/3 and \((\sqrt{5}+1)/2\), respectively. We further present an optimal algorithm and prove its competitive ratio reaches the lower bound.     

Serve or skip: the power of rejection in online bottleneck matching

We consider the online matching problem, where n server-vertices lie in a metric space and n request-vertices that arrive over time each must immediately be permanently assigned to a server-vertex. We focus on the egalitarian bottleneck objective, where the goal is to minimize the maximum distance between any request and its server. It has been shown that while there are effective algorithms for the utilitarian objective (minimizing total cost) in the resource augmentation setting where the offline adversary has half the resources, these are not effective for the egalitarian objective. Thus, we propose a new Serve-or-Skip (SoS) bicriteria analysis model, where the online algorithm may reject or skip up to a specified number of requests, and propose two greedy algorithms: GriNN(t) and \({{\textsc {Grin}}^*(t)}\). We show that the SoS model of resource augmentation analysis can essentially simulate the doubled-server-capacity model, and then examine the performance of GriNN(t) and \({\textsc {Grin}^*(t)}\).     

Approximation algorithms for the bus evacuation problem

We consider the bus evacuation problem. Given a positive integer B, a bipartite graph G with parts S and \(T \cup \{r\}\) in a metric space and functions \(l_i :S \rightarrow {\mathbb {Z}}_+\) and \({u_j :T \rightarrow \mathbb {Z}_+ \cup \{\infty \}}\), one wishes to find a set of B walks in G. Every walk in B should start at r and finish in T and r must be visited only once. Also, among all walks, each vertex i of S must be visited at least \(l_i\) times and each vertex j of T must be visited at most \(u_j\) times. The objective is to find a solution that minimizes the length of the longest walk. This problem arises in emergency planning situations where the walks correspond to the routes of B buses that must transport each group of people in S to a shelter in T, and the objective is to evacuate the entire population in the minimum amount of time. In this paper, we prove that approximating this problem by less than a constant is \(\text{ NP }\)-hard and present a 10.2-approximation algorithm. Further, for the uncapacitated BEP, in which \(u_j\) is infinity for each j, we give a 4.2-approximation algorithm.     

Asymptotically optimal policy for stochastic job shop scheduling problem to minimize makespan

This paper studies the large-scale stochastic job shop scheduling problem with general number of similar jobs, where the processing times of the same step are independently drawn from a known probability distribution, and the objective is to minimize the makespan. For the stochastic problem, we introduce the fluid relaxation of its deterministic counterpart, and define a fluid schedule for the fluid relaxation. By tracking the fluid schedule, a policy is proposed for the stochastic job shop scheduling problem. The expected value of the gap between the solution produced by the policy and the optimal solution is proved to be O(1), which indicates the policy is asymptotically optimal in expectation.     

A quadratic time exact algorithm for continuous connected 2-facility location problem in trees

This paper studies the continuous connected 2-facility location problem (CC2FLP) in trees. Let \(T = (V, E, c, d, \ell , \mu )\) be an undirected rooted tree, where each node \(v \in V\) has a weight \(d(v) \ge 0\) denoting the demand amount of v as well as a weight \(\ell (v) \ge 0\) denoting the cost of opening a facility at v, and each edge \(e \in E\) has a weight \(c(e) \ge 0\) denoting the cost on e and is associated with a function \(\mu (e,t) \ge 0\) denoting the cost of opening a facility at a point x(e, t) on e where t is a continuous variable on e. Given a subset \(\mathcal {D} \subseteq V\) of clients, and a subset \(\mathcal {F} \subseteq \mathcal {P}(T)\) of continuum points admitting facilities where \(\mathcal {P}(T)\) is the set of all the points on edges of T, when two facilities are installed at a pair of continuum points \(x_1\) and \(x_2\) in \(\mathcal {F}\), the total cost involved in CC2FLP includes three parts: the cost of opening two facilities at \(x_1\) and \(x_2\), K times the cost of connecting \(x_1\) and \(x_2\), and the cost of all the clients in \(\mathcal {D}\) connecting to some facility. The objective is to open two facilities at a pair of continuum points in \(\mathcal {F}\) to minimize the total cost, for a given input parameter \(K \ge 1\). This paper focuses on the case of \(\mathcal {D} = V\) and \(\mathcal {F} = \mathcal {P}(T)\). We first study the discrete version of CC2FLP, named the discrete connected 2-facility location problem (DC2FLP), where two facilities are restricted to the nodes of T, and devise a quadratic time edge-splitting algorithm for DC2FLP. Furthermore, we prove that CC2FLP is almost equivalent to DC2FLP in trees, and develop a quadratic time exact algorithm based on the edge-splitting algorithm. Finally, we adapt our algorithms to the general case of \(\mathcal {D} \subseteq V\) and \(\mathcal {F} \subseteq \mathcal {P}(T)\).     

A sufficient condition for planar graphs to be (3, 1)-choosable

A (k, d)-list assignment L of a graph is a function that assigns to each vertex v a list L(v) of at least k colors satisfying \(|L(x)\cap L(y)|\le d\) for each edge xy. An L-coloring is a vertex coloring \(\pi \) such that \(\pi (v) \in L(v)\) for each vertex v and \(\pi (x) \ne \pi (y)\) for each edge xy. A graph G is (k, d)-choosable if there exists an L-coloring of G for every (k, d)-list assignment L. This concept is known as choosability with separation. In this paper, we will use Thomassen list coloring extension method to prove that planar graphs with neither 6-cycles nor adjacent 4- and 5-cycles are (3, 1)-choosable. This is a strengthening of a result obtained by using Discharging method which says that planar graphs without 5- and 6-cycles are (3, 1)-choosable.     

An asymptotically optimal algorithm for large-scale mixed job shop scheduling to minimize the makespan

This paper considers the large-scale mixed job shop scheduling problem with general number of jobs on each route. The problem includes ordinary machines, batch machines (with bounded or unbounded capacity), parallel machines, and machines with breakdowns. The objective is to find a schedule to minimize the makespan. For the problem, we define a virtual problem and a corresponding virtual schedule, based on which our algorithm TVSA is proposed. The performance analysis of the algorithm shows the gap between the obtained solution and the optimal solution is O(1), which indicates the algorithm is asymptotically optimal.     

Cost sharing on prices for games on graphs

Let \(N=\{1,\dots ,n\}\) be a set of customers who want to buy a single homogenous goods in market. Let \(q_i>0\) be the quantity that \(i\in N\) demands, \(q=(q_1,\dots ,q_n)\) and \(q_S=\sum _{i\in S}q_i\) for \(S\subseteq N\). If f(s) is a (increasing and concave) cost function, then it yields a cooperative game (N, f, q) by defining characteristic function \(v(S)=f(q_S)\) for \(S\subseteq N\). We now consider the way of taking packages of goods by customers and define a communication graph L on N, in which i and j are linked if they can take packages for each other. So if i and j are connected, then a package can be delivered from i to j by some intermediators. We thus admit any connected subset as a feasible coalition, and obtain a game (N, f, q, L) by defining characteristic function \(v_L(S)=\sum _{R\in S/L}f(q_R)\) for \(S\subseteq N\), where S / L is the family of induced components (maximal connected subset) in S. It is shown that there is an allocation (cost shares) \(x=(x_1,\dots ,x_n)\) from the core for the game (\(x_S\le v_L(S)\) for any \(S\subseteq N\)) such that x satisfies Component Efficiency and Ranking for Unit Prices. If f(s) and q satisfy some further condition, then there is an allocation x from the core such that x satisfies Component Efficiency, and \(x_i \le x_j\) and \(\frac{x_i}{q_i} \ge \frac{x_j}{q_j}\) if \(q_i \le q_j\) for i and j in the same component of N.     

A compact representation for minimizers of <Emphasis Type="Italic">k</Emphasis>-submodular functions

A k-submodular function is a generalization of submodular and bisubmodular functions. This paper establishes a compact representation for minimizers of a k-submodular function by a poset with inconsistent pairs (PIP). This is a generalization of Ando–Fujishige’s signed poset representation for minimizers of a bisubmodular function. We completely characterize the class of PIPs (elementary PIPs) arising from k-submodular functions. We give algorithms to construct the elementary PIP of minimizers of a k-submodular function f for three cases: (i) a minimizing oracle of f is available, (ii) f is network-representable, and (iii) f arises from a Potts energy function. Furthermore, we provide an efficient enumeration algorithm for all maximal minimizers of a Potts k-submodular function. Our results are applicable to obtain all maximal persistent labelings in actual computer vision problems. We present experimental results for real vision instances.     

The Best-or-Worst and the Postdoc problems

We consider two variants of the secretary problem, the Best-or-Worst and the Postdoc problems, which are closely related. First, we prove that both variants, in their standard form with binary payoff 1 or 0, share the same optimal stopping rule. We also consider additional cost/perquisites depending on the number of interviewed candidates. In these situations the optimal strategies are very different. Finally, we also focus on the Best-or-Worst variant with different payments depending on whether the selected candidate is the best or the worst.     

A characterization of linearizable instances of the quadratic minimum spanning tree problem

We investigate special cases of the quadratic minimum spanning tree problem (QMSTP) on a graph \(G=(V,E)\) that can be solved as a linear minimum spanning tree problem. We give a characterization of such problems when G is a complete graph, which is the standard case in the QMSTP literature. We extend our characterization to a larger class of graphs that include complete bipartite graphs and cactuses, among others. Our characterization can be verified in \(O(|E|^2)\) time. In the case of complete graphs and when the cost matrix is given in factored form, we show that our characterization can be verified in O(|E|) time. Related open problems are also indicated.     

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