ﻻ يوجد ملخص باللغة العربية
In this paper the problem of scheduling of jobs on parallel machines under incompatibility relation is considered. In this model a binary relation between jobs is given and no two jobs that are in the relation can be scheduled on the same machine. In particular, we consider job scheduling under incompatibility relation forming bipartite graphs, under makespan optimality criterion, on uniform and unrelated machines. We show that no algorithm can achieve a good approximation ratio for uniform machines, even for a case of unit time jobs, under $P eq NP$. We also provide an approximation algorithm that achieves the best possible approximation ratio, even for the case of jobs of arbitrary lengths $p_j$, under the same assumption. Precisely, we present an $O(n^{1/2-epsilon})$ inapproximability bound, for any $epsilon > 0$; and $sqrt{p_{sum}}$-approximation algorithm, respectively. To enrich the analysis, bipartite graphs generated randomly according to Gilberts model $mathcal{G}_{n,n,p(n)}$ are considered. For a broad class of $p(n)$ functions we show that there exists an algorithm producing a schedule with makespan almost surely at most twice the optimum. Due to our knowledge, this is the first study of randomly generated graphs in the context of scheduling in the considered model. For unrelated machines, an FPTAS for $R2|G = bipartite|C_{max}$ is provided. We also show that there is no algorithm of approximation ratio $O(n^bp_{max}^{1-epsilon})$, even for $Rm|G = bipartite|C_{max}$ for $m ge 3$ and any $epsilon > 0$, $b > 0$, unless $P = NP$.
In this paper we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first non-trivial algorithm, with running time $O(mn)$, dates back to K{o}nigs work in 1916 (here $m=nd$ is the number of ed
In the scheduling with non-uniform communication delay problem, the input is a set of jobs with precedence constraints. Associated with every precedence constraint between a pair of jobs is a communication delay, the time duration the scheduler has t
We give a 1.488-approximation for the classic scheduling problem of minimizing total weighted completion time on unrelated machines. This is a considerable improvement on the recent breakthrough of $(1.5 - 10^{-7})$-approximation (STOC 2016, Bansal-S
The parallel machine scheduling problem has been a popular topic for many years due to its theoretical and practical importance. This paper addresses the robust makespan optimization problem on unrelated parallel machine scheduling with sequence-depe
We study the early work scheduling problem on identical parallel machines in order to maximize the total early work, i.e., the parts of non-preemptive jobs executed before a common due date. By preprocessing and constructing an auxiliary instance whi