$3/2$-approximation algorithm for a single machine scheduling problem

N. S. Grigoreva

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 17 (2021) no. 3, pp. 240-253

Résumé

The problem of minimizing the maximum delivery times while scheduling tasks on a single processor is a classical combinatorial optimization problem. Each task $u_i$ must be processed without interruption for $ t (u_i)$ time units on the machine, which can process at most one task at time. Each task $u_i$ has a release time $r (u_i)$, when the task is ready for processing, and a delivery time $q (u_i)$. Its delivery begins immediately after processing has been completed. The objective is to minimize the time, by which all jobs are delivered. In the Graham notation this problem is denoted by $1|r_j,q_j|C_{\max},$ it has many applications and it is NP-hard in a strong sense. The problem is useful in solving owshop and jobshop scheduling problems. The goal of this article is to propose a new $3/2$-approximation algorithm, which runs in $O(n\log n)$ times for scheduling problem $1|r_j,q_j|C_{\max}$. An example is provided which shows that the bound of $3/2$ is accurate. To compare the effectiveness of proposed algorithms, random generated problems of up to $5000$ tasks were tested.

Détail

Keywords: single-machine scheduling problem, realize and delivery times, approximation algorithm, guarantee approximation ratio.