Geodesic
$3/2$-approximation algorithm for a single machine scheduling problem
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 17 (2021) no. 3, pp. 240-253 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: single-machine scheduling problem, realize and delivery times, approximation algorithm, guarantee approximation ratio. 
@article{VSPUI_2021_17_3_a1,
     author = {N. S. Grigoreva},
     title = {$3/2$-approximation algorithm for a single machine scheduling problem},
     journal = {Vestnik Sankt-Peterburgskogo universiteta. Prikladna\^a matematika, informatika, processy upravleni\^a},
     pages = {240--253},
     year = {2021},
     volume = {17},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSPUI_2021_17_3_a1/}
}
TY  - JOUR
AU  - N. S. Grigoreva
TI  - $3/2$-approximation algorithm for a single machine scheduling problem
JO  - Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
PY  - 2021
SP  - 240
EP  - 253
VL  - 17
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VSPUI_2021_17_3_a1/
LA  - ru
ID  - VSPUI_2021_17_3_a1
ER  - 
%0 Journal Article
%A N. S. Grigoreva
%T $3/2$-approximation algorithm for a single machine scheduling problem
%J Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
%D 2021
%P 240-253
%V 17
%N 3
%U http://geodesic.mathdoc.fr/item/VSPUI_2021_17_3_a1/
%G ru
%F VSPUI_2021_17_3_a1
N. S. Grigoreva. $3/2$-approximation algorithm for a single machine scheduling problem. Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 17 (2021) no. 3, pp. 240-253. http://geodesic.mathdoc.fr/item/VSPUI_2021_17_3_a1/

[1] Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., “Optimization and approximation in deterministic sequencing and scheduling: A survey”, Annals of Discrete Mathematics, 5:10 (1979), 287–326 | DOI | Zbl

[2] Lenstra J. K., Rinnooy Kan A. H. G., Brucker P., “Complexity of machine scheduling problems”, Annals of Discrete Mathematics, 1 (1977), 343–362 | DOI | Zbl

[3] Lazarev A. A., Sadykov R. R., Sevastyanov S. V., “A scheme of approximation solution of problem $1|r_i|L_{\max}$”, Discrete analyze and operation research. Series 2, 13:1 (2006), 57–76 (In Russian) | Zbl

[4] Baker K. R., Introduction to sequencing and scheduling, John Wiley $\$ Son, New York, 1974, 318 pp.

[5] Kanet J. J., Sridharan V., “Scheduling with inserted idle time: problem taxonomy and literature review”, Operations Research, 48:1 (2000), 99–110 | DOI

[6] Grigoreva N. S., “Branch and bound algorithm for multiprocessor scheduling problem”, Vestnik of Saint Petersburg University. Series 10. Applied Mathematics. Computer Science. Control Processes, 2009, no. 1, 44–55 (In Russian)

[7] Grigoreva N. S., “Scheduling problem to minimize the maximum lateness for parallel processors”, Vestnik of Saint Petersburg University. Series 10. Applied Mathematics. Computer Science. Control Processes, 2016, no. 4, 51–65 (In Russian)

[8] Grigoreva N. S., “Multiprocessor scheduling with inserted idle time to minimize the maximum lateness”, Proceedings of the 7th Multidisciplinary International Conference of Scheduling: Theory and Applications, MISTA, Prague, 2015, 814–816

[9] Grigoreva N. S., “Single machine inserted idle time scheduling with release times and due dates”, Proceedings. DOOR2016 (Vladivostoc, Russia. September 19–23, 2016), Ceur-WS, 1623, 2016, 336–343

[10] Schrage L., Optimal solutions to resource constrained network scheduling problems, Unpublished manuscript, 1971

[11] Kise H., Ibaraki T., Mine H., “Performance analysis of six approximation algorithms for the one-machine maximum lateness scheduling problem with ready times”, Journal of the Operations Research Society of Japan, 22 (1979), 205–224 | DOI | Zbl

[12] Potts C. N., “Analysis of a heuristic for one machine sequencing with release dates and delivery times”, Operations Research, 28 (1980), 1436–1441 | DOI | Zbl

[13] Hall L. A., Shmoys D. B., “Jackson's rule for single-machine scheduling: making a good heuristic better”, Mathematics of Operations Research, 17:1 (1992), 22–35 | DOI | Zbl

[14] Nowicki E., Smutnicki C., “An approximation algorithm for a single-machine scheduling problem with release times and delivery times”, Discrete Applied Mathematics, 48 (1994), 69–79 | DOI | Zbl

[15] Hall L. A., Shmoys D. B., “Approximation algorithms for constrained scheduling problems”, Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1989, 134–139 | DOI

[16] Mastrolilli M., “Efficient approximation schemes for scheduling problems with release dates and delivery times”, Journal of Scheduling, 6 (2003), 521–531 | DOI | Zbl

[17] Carlier J., “The one machine sequencing problem”, European Journal of Operational Research, 11 (1982), 42–47 | DOI | Zbl