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.     

Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan

We study the online scheduling problem on m identical parallel machines to minimize makespan, i.e., the maximum completion time of the jobs, where m is given in advance and the jobs arrive online over time. We assume that the jobs, which arrive at some nonnegative real times, are of equal-length and are restricted by chain precedence constraints. Moreover, the jobs arriving at distinct times are independent, and so, only the jobs arriving at a common time are restricted by the chain precedence constraints. In the literature, a best possible online algorithm of a competitive ratio 1.3028 is given for the case \(m=2\). But the problem is unaddressed for \(m\ge 3\). In this paper, we present a best possible online algorithm for the problem with \(m\ge 3\), where the algorithm has a competitive ratio of 1.3028 for \(3\le m\le 5\) and 1.3146 for \(m\ge 6\).     

具有最大总加权满意度的单机调度问题的dynasearch算法

研究了总加权满意程度最大化的单机调度问题.对最优解的性质进行分析和证明,提出该类问题的统治规则.提出该问题新的基于dynasearch 邻域的迭代局域搜索算法(ILS).算法主要特点:1)dynasearch 是基于多摄动的思想,即一次可以做多个相互独立的交换(或插入);2)用动态规划获得最优dynasearch移动;3)ILS采用随机kick 策略对局部最优解进行摄动,然后继续迭代.实现了该问题的两种dynaearch算法;把两种dynasearch算法与统治规则相结合;在进行kick时引入误差限制.实验表明:嵌入统治规则的算法优于没有统治规则的算法;基于dynasearch交换的ILS 优于基于dynasearch插入的ILS;dynaearch算法要优于以交换为邻域的多初始点改进算法.     

Online LPT algorithms for parallel machines scheduling with a single server

We consider two parallel machines scheduling problems with a single server. For the general case we present an online LPT algorithm with competitive ratio 2, and give a lower bound $\frac{\sqrt{5} + 1}{2}$ . We also apply the online LPT algorithm to the special case where all the setup times are equal to 1. We show that the competitive ratio is 1.5, and no online algorithm can has a competitive ratio less than  $\sqrt{2}$ .     

Near optimal algorithms for online weighted bipartite matching in adversary model

Bipartite matching is an important problem in graph theory. With the prosperity of electronic commerce, such as online auction and AdWords allocation, bipartite matching problem has been extensively studied under online circumstances. In this work, we study the online weighted bipartite matching problem in adversary model, that is, there is a weighted bipartite graph \(G=(L,R,E)\) and the left side L is known as input, while the vertices in R come one by one in an order arranged by the adversary. When each vertex in R comes, its adjacent edges and relative weights are revealed. The algorithm should irreversibly decide whether to match this vertex to an unmatched neighbor in L with the objective to maximize the total weight of the obtained matching. When the weights are unbounded, the best algorithm can only achieve a competitive ratio \(\varTheta \left( \frac{1}{n}\right) \), where n is the number of vertices coming online. Thus, we mainly deal with two variants: the bounded weight problem in which all weights are in the range \([\alpha , \beta ]\), and the normalized summation problem in which each vertex in one side has the same total weights. We design algorithms for both variants with competitive ratio \(\varTheta \left( \max \left\{ \frac{1}{\log \frac{\beta }{\alpha }},\frac{1}{n}\right\} \right) \) and \(\varTheta \left( \frac{1}{\log n}\right) \) respectively. Furthermore, we show these two competitive ratios are tight by providing the corresponding hardness results.     

Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree

Given a simple, undirected graph G=(V,E) and a weight function w:E→ℤ⁺, we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. It has previously been shown that the unweighted version of the problem is solvable in polynomial time while the weighted version is (weakly) NP-hard. In this paper, we strengthen these results as follows: (1) We prove that the weighted version is strongly NP-hard even if all edge weights belong to the set {1,k}, where k is any fixed integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm for this problem whose approximation ratio is smaller than (1+1/k) unless P = NP; (2) we present a new polynomial-time algorithm that approximates the general version of the problem within a ratio of (2−1/k), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1,k} within a ratio of 3/2 for k=2 (note that this matches the inapproximability bound above), and (2−2/(k+1)) for any k≥3, respectively, in polynomial time.     

Online set multicover algorithms for dynamic D2D communications

Motivated by the dynamic resource allocation problem for device-to-device (D2D) communications, we study the online set multicover problem (OSMC). In the online set multicover, the set X of elements to be covered is unknown in advance; furthermore, the coverage requirement of each element \(x \in X\) is initially unknown. Elements of X together with coverage requirements are presented one at a time in an online fashion; and a feasible solution must be maintained at all times. We provide the first deterministic, online algorithms for OSMC with competitive ratios. We consider two versions of OSMC; in the first, each set may be picked only once, while the second version allows each set to be picked multiple times. For both versions, we present the first deterministic, online algorithms, with competitive ratios \(O( \log n \log m )\) and \(O( \log n (\log m + \log k) )\), repectively, where n is the number of elements, m is the number of sets, and k is the maximum coverage requirement. By simulation, we show the efficacy of these algorithms for resource allocation in the D2D setting by analyzing network throughput and other metrics, obtaining a large improvement in running time over offline methods.     

Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart

We consider the online scheduling of equal length jobs on unbounded parallel batch processing machines to minimize makespan with limited restart. In the problem \(m\) identical unbounded parallel batch processing machines are available to process the equal length jobs arriving over time. The processing batches are allowed limited restart. Here, “restart” means that a running task may be interrupted, losing all the work done on it, and the jobs in the interrupted task are then released and become independently unscheduled jobs, called restarted jobs. “Limited restart” means that only a running batch that contains no restarted jobs can be restarted. For this problem, we present a best possible online algorithm.     

Online graph exploration algorithms for cycles and trees by multiple searchers

This paper deals with online graph exploration problems by multiple searchers. The information on the graph is given online. As the exploration proceeds, searchers gain more information on the graph. Assuming an appropriate communication model among searchers, searchers can share the information about the environment. Thus, a searcher must decide which vertex to visit next based on the partial information on the graph gained so far by searchers. We assume that all searchers initially start the exploration at the origin vertex, and the goal is that each vertex is visited by at least one searcher and all searchers finally return to the origin vertex. The objective is to minimize the time when the goal is achieved. We study the case of cycles and trees. For the former, we give an optimal online exploration algorithm in terms of competitive ratio, and for the latter, we also give an online exploration algorithm which is optimal among greedy algorithms.     

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

A better constant-factor approximation for weighted dominating set in unit disk graph

This paper presents a (10+ε)-approximation algorithm to compute minimum-weight connected dominating set (MWCDS) in unit disk graph. MWCDS is to select a vertex subset with minimum weight for a given unit disk graph, such that each vertex of the graph is contained in this subset or has a neighbor in this subset. Besides, the subgraph induced by this vertex subset is connected. Our algorithm is composed of two phases: the first phase computes a dominating set, which has approximation ratio 6+ε (ε is an arbitrary positive number), while the second phase connects the dominating sets computed in the first phase, which has approximation ratio 4. This work is supported in part by National Science Foundation under grant CCF-9208913 and CCF-0728851; and also supported by NSFC (60603003) and XJEDU.     

A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs

In the minimum weighted dominating set problem (MWDS), we are given a unit disk graph with non-negative weight on each vertex. The MWDS seeks a subset of the vertices of the graph with minimum total weight such that each vertex of the graph is either in the subset or adjacent to some nodes in the subset. A?weight function is called smooth, if the ratio of the weights of any two adjacent nodes is upper bounded by a constant. MWDS is known to be NP-hard. In this paper, we give the first polynomial time approximation scheme (PTAS) for MWDS with smooth weights on unit disk graphs, which achieves a (1+ε)-approximation for MWDS, for any ε>0.     

Online algorithms for 1-space bounded multi dimensional bin packing and hypercube packing

In this paper, we study 1-space bounded multi-dimensional bin packing and hypercube packing. A sequence of items arrive over time, each item is a d-dimensional hyperbox (in bin packing) or hypercube (in hypercube packing), and the length of each side is no more than 1. These items must be packed without overlapping into d-dimensional hypercubes with unit length on each side. In d-dimensional space, any two dimensions i and j define a space P _ij . When an item arrives, we must pack it into an active bin immediately without any knowledge of the future items, and 90^°-rotation on any plane P _ij is allowed. The objective is to minimize the total number of bins used for packing all these items in the sequence. In the 1-space bounded variant, there is only one active bin for packing the current item. If the active bin does not have enough space to pack the item, it must be closed and a new active bin is opened. For d-dimensional bin packing, an online algorithm with competitive ratio 4 ^d is given. Moreover, we consider d-dimensional hypercube packing, and give a 2 ^d+1-competitive algorithm. These two results are the first study on 1-space bounded multi dimensional bin packing and hypercube packing.     

Approximation for maximizing monotone non-decreasing set functions with a greedy method

We study the problem of maximizing a monotone non-decreasing function \(f\) subject to a matroid constraint. Fisher, Nemhauser and Wolsey have shown that, if \(f\) is submodular, the greedy algorithm will find a solution with value at least \(\frac{1}{2}\) of the optimal value under a general matroid constraint and at least \(1-\frac{1}{e}\) of the optimal value under a uniform matroid \((\mathcal {M} = (X,\mathcal {I})\), \(\mathcal {I} = \{ S \subseteq X: |S| \le k\}\)) constraint. In this paper, we show that the greedy algorithm can find a solution with value at least \(\frac{1}{1+\mu }\) of the optimum value for a general monotone non-decreasing function with a general matroid constraint, where \(\mu = \alpha \), if \(0 \le \alpha \le 1\); \(\mu = \frac{\alpha ^K(1-\alpha ^K)}{K(1-\alpha )}\) if \(\alpha > 1\); here \(\alpha \) is a constant representing the “elemental curvature” of \(f\), and \(K\) is the cardinality of the largest maximal independent sets. We also show that the greedy algorithm can achieve a \(1 - (\frac{\alpha + \cdots + \alpha ^{k-1}}{1+\alpha + \cdots + \alpha ^{k-1}})^k\) approximation under a uniform matroid constraint. Under this unified \(\alpha \)-classification, submodular functions arise as the special case \(0 \le \alpha \le 1\).     

Multi-agent scheduling on a single machine with a fixed number of competing agents to minimize the weighted sum of number of tardy jobs and makespans

We study the multi-agent scheduling on a single machine with a fixed number of competing agents, in which, the objective function of each agent is either the number of tardy jobs or the makespan, and the goal of the problem is to minimize the weighted sum of agents’ objective functions. In the literature, the computational complexity of this problem was posed as open. By using enumerating, dynamic programming, and schedule-configuration, we show in this paper that the problem is solvable in polynomial time.     

差异分批模式下的联合成本优化问题及算法

提出了一类制造企业的联合成本优化问题,将企业的产品制造环节和配送环节进行协同运作,实现供应链环境下的联合调度.在生产环节,考虑一类典型的差异分批制造模式,即待加工的作业尺寸有差异,而批处理设备的容量确定,设备环境为多台并行设备;在配送环节,企业采用自有车辆进行运输,车辆具有相同的运输能力;若完工的作业在当前无可用车辆进行配送,则转入产成品库存;联合成本为生产、库存和配送三阶段的总成本.本文首先构造了基于整数规划的数学模型,证明了联合成本的最小化问题是强NP-hard问题;然后设计了多项式时间的近似算法,分析了算法的时间复杂性,并证明了算法的求解性能.