به حداقل رساندن زمان اتمام وزنی در یک دستگاه واحد با یک فاصله غیرثابت در دسترس: دیفرانسیل تقریبی

This paper is the first successful attempt on differential approximability study for a scheduling problem. Such a study considers the weighted completion time minimization on a single machine with a fixed non-availability interval. The analysis shows that the Weighted Shortest Processing Time (WSPT) rule cannot yield a differential approximation for the problem under consideration in the general case. Nevertheless, a slight modification of this rule provides an approximation with a differential ratio of View the MathML source

In this paper, we study the differential approximability of a well-known scheduling problem. Our work is motivated by the fact that the differential approximability concept has not yet been investigated for scheduling problems. Contrary to the standard approximability based on the comparison in the worst case of a heuristic solution to the optimal one, the differential approximability principle consists in comparing the heuristic solution to both the optimal and the worst solutions. More precisely, we say that heuristic AA is an αα-differential approximation for problem ΠΠ if for every instance II of ΠΠ the following relation holds View the MathML sourcef(A(I))⩽αf(opt(I))+(1−α)f(wst(I)), where ff is the objective function to be minimized in problem ΠΠ and the values View the MathML sourceopt(I),A(I) and View the MathML sourcewst(I) denote respectively the values of an optimal solution, of an approximate solution and of a worst solution. The latter solution is defined as the optimal solution of a problem having the same instances and set of constraints as the initial problem but the opposite goal (i.e., maxmax, if the initial problem is a minimization one and minmin if the initial problem is a maximization problem). Let us also note that worst solutions are not always easy to compute. For instance, for the minimization version of the travelling salesman problem, the worst solution is a Hamiltonian cycle of maximum total distance, i.e., the optimum solution of the maximum travelling salesman problem. The computation of such a solution is not trivial since the latter problem is as hard as the former one. On the contrary, examples of problems for which a worst solution is easily computed are maximum independent set where the worst solution is the empty set, minimum vertex cover, where this solution is the whole vertex-set of the input graph, or, even, minimum graph-colouring, where the worst solution consists in taking a colour per vertex of the input graph. The value αα is called the differential ratio and it belongs to (0,1)(0,1). For more details on these approaches, the reader is invited to consult Ausiello and Paschos [1], Demange and Paschos [2], and Hassin and Khuller [3].

Motivated by the absence in the literature of differential approximability analysis for scheduling problems, this paper aims to investigate this new direction. The considered study is related to the weighted completion time minimization on a single machine with a fixed non-availability interval. The analysis of the Weighted Shortest Processing Time (View the MathML sourceWSPT) rule shows that this rule cannot yield a differential approximation for the problem under consideration in the general case. Nevertheless, a slight modification of this rule provides a View the MathML source3−52-differential approximation. Ongoing research will aim at designing more efficient differential approximations for scheduling problems (in particular, differential approximation schemes).