Estimates of the absolute error and a scheme for an approximate solution to scheduling problems

A. A. Lazarev

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 49 (2009) no. 2, pp. 382-396

Résumé

An approach is proposed for estimating absolute errors and finding approximate solutions to classical NP-hard scheduling problems of minimizing the maximum lateness for one or many machines and makespan is minimized. The concept of a metric (distance) between instances of the problem is introduced. The idea behind the approach is, given the problem instance, to construct another instance for which an optimal or approximate solution can be found at the minimum distance from the initial instance in the metric introduced. Instead of solving the original problem (instance), a set of approximating polynomially/pseudopolynomially solvable problems (instances) are considered, an instance at the minimum distance from the given one is chosen, and the resulting schedule is then applied to the original instance.

Bibliographie

[1] Graham R. L., Lawler E. L., Lenstra J. K. et al., “Optimization and approximation in deterministic sequencing and scheduling: a survey”, Ann. Discrete Math., 5 (1979), 287–326 | DOI | MR | Zbl

[2] Lenstra J. K., Rinnooy Kan A. H. G., Brucker P., “Complexity of machine scheduling problems”, European J. Operat. Res., 4 (1980), 270–275 | DOI | MR | Zbl

[3] Jackson J. R., Scheduling a production line to minimize maximum tardiness, Manag. Sci. Res. Project, UCLA, 1955, 43

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

[5] Hall L. A., Shmoys D. B., “Jackson's rule for one-machine scheduling: making a good heuristic better”, Math. Operat. Res., 17 (1992), 22–35 | DOI | MR | Zbl

[6] Mastrolilli M., “Efficient approximation schemes for scheduling problems with release dates and deilivery times”, J. Schedling, 6 (2003), 521–531 | DOI | MR | Zbl

[7] Lawler E. L., “Optimal sequencing of a single machine subject to precedence constraints”, Manag. Sci., 19:5 (1973), 544–546 | DOI | Zbl

[8] Simons B. B., “A fast algorithm for single processor scheduling”, Proc. 19th IEEE Ann. Symp. on Foundations of Computer Science, Ann. Arbor. Mich., New York, 1978, 246–252 | MR

[9] Baker K. R., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., “Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints”, Operat. Res., 31 (1983), 381–386 | DOI

[10] Hoogeveen J. A., “Minimizing maximum promptness and maximum lateness on a single machine”, Math. Operat. Res., 21 (1996), 100–114 | DOI | MR | Zbl

[11] Lazarev A. A., Shulgina O. H., “Psevdopolinomialnyi algoritm resheniya NP-trudnoi zadachi minimizatsii maksimalnogo vremennogo smescheniya”, Tr. X mezhdunar. Baikalskoi shkoly-seminara “Metody optimizatsii i ikh prilozh.” (5–12 iyulya), Baikal, Irkutsk, 1998, 163–167

[12] Lazarev A. A., Shulgina O. N., Polinomialno razreshimye chastnye sluchai zadachi minimizatsii maksimalnogo vremennogo smescheniya, Dep. v VINITI 28.11.00, No 3019-V00, Kazanskii un-t, Kazan, 2000, Izv. vuzov. Matematika

[13] Finkelshtein Yu. Yu., Priblizhennye metody i prikladnye zadachi diskretnogo programmirovaniya, Nauka, M., 1976

[14] Brucker P., Garey M. R., Johnson D. S., “Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness”, Math. Operat. Res., 2:3 (1977), 275–284 | DOI | MR | Zbl

[15] Du J., Leung J. Y.-T., Young G. H., “Scheduling chain-structered tasks to minimize makespan and mean flow time”, Inform. and Comput., 92:2 (1991), 219–236 | DOI | MR | Zbl

[16] Garey M. R., Johnson D. S., ““Strong” NP-completeness results: motivation, examples, and implications”, J. Assoc. Comput. Machinery, 25:3 (1978), 499–508 | MR | Zbl

[17] Ullman J. D., “NP-complete scheduling problems”, J. Comput. System Sci., 10 (1975), 384–393 | MR | Zbl

[18] Lazarev A. A., Sadykov P. P., Sevastyanov C. B., “Skhema priblizhennogo resheniya problemy $1|R_j|L_{\max}$”, Diskretnyi analiz i issledovanie operatsii. Ser. 2, 13:1 (2006), 57–76 | MR

[19] Garey M. R., Johnson D. S., “Schduling tasks with nonuniform deadlines on two processors”, J. Assoc. Comput. Machinery, 23 (1976), 461–467 | MR | Zbl

[20] Garey M. R., Johnson D. S., “Two-rpocessor scheduling with start-times and deadlines”, SIAM J. Comput., 6:3 (1977), 416–426 | DOI | MR | Zbl

[21] Brucker P., Hurink J., Kubiak W., “Scheduling identical jobs with chain precedence constraints on two uniform machines”, Math. Meth. Operat. Res., 49:2 (1999), 211–219 | MR | Zbl

[22] Kubiak W., Exact and approximate algorithms for scheduling unit time tasks with trre-like precedence constraints, Abstr. EURO IX-TIMS XXVIII, Paris, 1988, 195

[23] Simons B., “Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines”, SIAM J. Comput., 2 (1983), 294–299 | DOI | MR

[24] Davida G. I., Linton D. J., “A new algorithm for the scheduling of tree strcutures tasks”, Proc. Conf. Inform. Sci. and Systems, Baltimore, MD, 1976, 543–548

[25] Hu T. C., “Parallel sequencing and assembly line problems”, Operat. Res., 9 (1961), 841–848 | DOI | MR

[26] Baptiste P., Brucker P., Knust S., Timkovsky V., “Ten notes on equal-execution-time scheduling”, Quarterly Journal of Operations. Research, 2 (2004), 111–127 | MR | Zbl

[27] Leung J. Y.-T., Dornberger O., Witthoff J. D., “On some variants of the bandwidth minimization problem”, SIAM J. Comput., 13:3 (1984), 650–667 | DOI | MR | Zbl

[28] Timkovsky V. G., “Identical parallel machines vs. unit-time shops and preemptions vs. chains inscheduling complexity”, European J. Operat. Res., 149:2 (2003), 355–376 | DOI | MR | Zbl

[29] Brucker P., Knust S., “Complexity results for single-machine problems with positive finish-start time-lags”, Computing., 63 (1999), 299–316 | DOI | MR | Zbl

[30] Johnson S. M., “Optimal two- and three-stage production schedules with setup times included”, Naval Res. Logistics Quarterly, 1 (1954), 61–68 | DOI

[31] Bruno J., Jones III J. W., So K., “Deterministic scheduling with pipelined processors”, IEEE Trans. Comput., 29:4 (1980), 308–316 | DOI | MR | Zbl

[32] Lazarev A. A., “Pareto-optimalnoe mnozhestvo NP-trudnoi zadachi minimizatsii maksimalnogo vremennogo smescheniya”, Izv. RAN. Teoriya i sistemy upravleniya, 2006, no. 6, 103–110 | MR

[33] Lazarev A. A., “Otsenka absolyutnoi pogreshnosti zadach teorii raspisanii s kriteriem minimizatsii maksimalnogo vremennogo smescheniya”, Dokl. RAN, 415:4 (2007), 446–449 | MR | Zbl

[34] Lazarev A.A., Effektivnye algoritmy resheniya nekotorykh zadach teorii raspisanii dlya odnogo pribora s direktivnymi srokami obsluzhivaniya trebovanii, Dis. $\dots$ kand. fiz.-matem. nauk, Un-t, Kazan, 1989, 108 pp.