zbMATH — the first resource for mathematics

Discrete optimization with polynomially detectable boundaries and restricted level sets. (English) Zbl 1268.90034
Summary: The paper describes an optimization procedure for a class of discrete optimization problems which is defined by certain properties of the boundary of the feasible region and level sets of the objective function. It is shown that these properties are possessed, for example, by various scheduling problems, including a number of well-known NP-hard problems which play an important role in scheduling theory. For one of these problems the presented optimization procedure is compared with a version of the branch-and-bound algorithm by means of computational experiments.
90C10 Integer programming
90B35 Deterministic scheduling theory in operations research
Full Text: DOI
[1] Garey MR, Johnson DS (1976) Scheduling tasks with nonuniform deadlines on two processors. J ACM 23:461–467 · Zbl 0338.68048 · doi:10.1145/321958.321967
[2] Hoogeveen JA, van de Velde SL, Veltman B (1994) Complexity of scheduling multiprocessor tasks with prespecified processor allocations. Discrete Appl Math 55:259–272 · Zbl 0938.68671 · doi:10.1016/0166-218X(94)90012-4
[3] Lenstra JK, Rinnooy Kan AHG (1978) Complexity of scheduling under precedence constraints. Oper Res 26:22–35 · Zbl 0371.90060 · doi:10.1287/opre.26.1.22
[4] Pinedo M (2008) Scheduling: theory, algorithms, and systems, 3rd edn. Springer, Berlin
[5] Ullman JD (1975) NP-complete scheduling problems. J Comput Syst Sci 10:384–393 · Zbl 0313.68054 · doi:10.1016/S0022-0000(75)80008-0
[6] Zinder Y (2007) The strength of priority algorithms. In: Proceedings, MISTA, pp 531–537
[7] Zinder Y, Roper D (1995) A minimax combinatorial optimization problem on an acyclic directed graph: polynomial-time algorithms and complexity. In: Proceedings, A.C. Aitken centenary conference, pp 391–400
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.