Geodesic
Scheduling problem to minimize the maximum lateness for parallel processors
Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 4 (2016), pp. 51-65 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problem of minimizing the maximum lateness while scheduling tasks to parallel identical processors is a classical combinatorial optimization problem. It has many applications, and it is NP-hard. This problem relates to the scheduling problem and it is denoted by $P|r_j |L_{\mathrm{max}}$. The multiprocessor scheduling problem is defined as follows: tasks have to be executed on several parallel identical processors. We must find where and when each task will be executed, such that the maximum lateness is minimum. The duration, release time and due date of each task are known. Preemption on processors is not allowed. A lot of research in scheduling has concentrated on the construction of the nondelay schedule. A nondelay schedule is a feasible schedule in which no processor is kept idle at a time when it could begin processing a task. An inserted idle time schedule (IIT) as a feasible schedule in which the processor is kept idle at a time when it could begin processing a task. The goal of this paper is to propose an IIT schedule for the $P|r_j |L_{\rm max}$ problem. We propose an approximate IIT algorithm named ELS/IIT (earliest latest start/ inserted idle time) and depth first branch and bound algorithm, which produces a feasible IIT (inserted idle time) schedule for a fixed maximum lateness $L$. The algorithm may be used in a binary search mode to find the smallest maximum lateness. The branch and bound algorithm is based on the earliest latest start/ inserted idle time branching strategy. Two new dominance criterions between decision nodes are used. A new method for evaluating unfeasible partial solutions was designed. To illustrate the effectiveness of this approach we tested algorithms on instances, which were randomly generated with the number of jobs from 50 to 300. Refs 14. Tables 5.
Keywords: parallel identical processors, branch and bound algorithm, maximum lateness. 
@article{VSPUI_2016_4_a4,
     author = {N. S. Grigoreva},
     title = {Scheduling problem to minimize the maximum lateness for parallel processors},
     journal = {Vestnik Sankt-Peterburgskogo universiteta. Prikladna\^a matematika, informatika, processy upravleni\^a},
     pages = {51--65},
     year = {2016},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSPUI_2016_4_a4/}
}
TY  - JOUR
AU  - N. S. Grigoreva
TI  - Scheduling problem to minimize the maximum lateness for parallel processors
JO  - Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
PY  - 2016
SP  - 51
EP  - 65
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VSPUI_2016_4_a4/
LA  - ru
ID  - VSPUI_2016_4_a4
ER  - 
%0 Journal Article
%A N. S. Grigoreva
%T Scheduling problem to minimize the maximum lateness for parallel processors
%J Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ
%D 2016
%P 51-65
%N 4
%U http://geodesic.mathdoc.fr/item/VSPUI_2016_4_a4/
%G ru
%F VSPUI_2016_4_a4
N. S. Grigoreva. Scheduling problem to minimize the maximum lateness for parallel processors. Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 4 (2016), pp. 51-65. http://geodesic.mathdoc.fr/item/VSPUI_2016_4_a4/

[1] Brucker P., Scheduling algorithms, Springer, Heidelberg, 2007, 378 pp. | MR | Zbl

[2] Graham R. L., Lawner E. L., Kan R., “Optimization and approximation in deterministic sequencing and scheduling: A survey”, Ann. of Disc. Math., 5:10 (1979), 287–326 | DOI | MR | Zbl

[3] Lenstra J. A., Kan R., Brucker P., “Complexity of machine scheduling problems”, Ann. of Disc. Math., 1 (1977), 343–362 | DOI | MR | Zbl

[4] Brucker P., Garey M. R., Johnson D. S., “Scheduling equal-length tasks under tree-like precendence constraints to minimize maximum lateness”, Matematics of Operations Research, 1977, no. 2, 275–284 | DOI | Zbl

[5] Zinder Y., Singh G., “Preemptive scheduling on parallel processors with due dates”, Asia Pacific Journal of Operational Research, 22 (2005), 445–462 | DOI | MR | Zbl

[6] Baker K. R., Introduction to Sequencing and Scheduling, John Wiley Son, New York, 1974, 318 pp.

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

[8] Carlier J., “The one-machine sequencing problem”, European J. Oper. Res., 11:1 (1982), 42–47 | DOI | MR | Zbl

[9] Grigoreva N. S., “Branch and bound algorithm for multiprocessor scheduling problem”, Vestnik of Saint Petersburg University. Series 10. Applied mathematics. Comruter science. Control processes, 2009, no. 1, 44–55 (In Russian)

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

[11] Gusfield D., “Bounds for naive multiple machine scheduling with release times and deadlines”, Journal of Algorithms, 5 (1984), 1–6 | DOI | MR | Zbl

[12] Romanovskii I. V., Khristova N. P., “The solution of minimax problem by the method of dichotomy”, Computational mathematics and mathematical physics, 13:5 (1973), 200–209 (In Russian)

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

[14] Fernandez E., Bussell B., “Bounds the number of processors and time for multiprocessor optimal schedules”, IEEE Trans. on Computers, 4:11 (1973), 745–751 | DOI | MR