The aim of this paper is to develop improved polynomial-time approximation algorithms belonging to the family of the fully polynomial time approximation schemes (FPTAS) for a group of scheduling problems. In particular, the new technique provides a positive answer to a question posed more than three decades ago by Gens and Levner [G.V. Gens and E.V. Levner, Discrete Appl. Math. 3 (1981) 313–318]: “Can an epsilon-approximation algorithm be found for the minimization version of the job-sequencing-with-deadlines problem running with the same complexity as the algorithms for the maximization form of the problem?”

Accepted:

DOI: 10.1051/ro/2016021

Keywords: Job-sequencing-with-deadlines scheduling problem, approximation algorithm, FPTAS

^{1}; Levner, Eugene

^{2}

@article{RO_2016__50_4-5_681_0, author = {Elalouf, Amir and Levner, Eugene}, title = {Improving the solution complexity of the scheduling problem with deadlines: {A} general technique}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {681--687}, publisher = {EDP-Sciences}, volume = {50}, number = {4-5}, year = {2016}, doi = {10.1051/ro/2016021}, zbl = {1357.90052}, mrnumber = {3570524}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro/2016021/} }

TY - JOUR AU - Elalouf, Amir AU - Levner, Eugene TI - Improving the solution complexity of the scheduling problem with deadlines: A general technique JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2016 SP - 681 EP - 687 VL - 50 IS - 4-5 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2016021/ DO - 10.1051/ro/2016021 LA - en ID - RO_2016__50_4-5_681_0 ER -

%0 Journal Article %A Elalouf, Amir %A Levner, Eugene %T Improving the solution complexity of the scheduling problem with deadlines: A general technique %J RAIRO - Operations Research - Recherche Opérationnelle %D 2016 %P 681-687 %V 50 %N 4-5 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2016021/ %R 10.1051/ro/2016021 %G en %F RO_2016__50_4-5_681_0

Elalouf, Amir; Levner, Eugene. Improving the solution complexity of the scheduling problem with deadlines: A general technique. RAIRO - Operations Research - Recherche Opérationnelle, Volume 50 (2016) no. 4-5, pp. 681-687. doi : 10.1051/ro/2016021. http://www.numdam.org/articles/10.1051/ro/2016021/

Routing and dispatching of multiple mobile agents in integrated enterprises. Int. J. Prod. Econ. 145 (2013) 96–106. | DOI

, and ,An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem. J. Scheduling 16 (2013) 429–435. | DOI | MR | Zbl

, and .An improved FPTAS for restricted shortest path. Inf. Proc. Lett. 83 (2002) 287–291. | DOI | MR | Zbl

, and ,M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co. (1979). | MR | Zbl

Approximation algorithm for some scheduling problems. Eng. Cybernet. Soviet J. Comput. Syst. Sci. 16 (1978) 38–46. | MR

and ,Fast approximation algorithm for job sequencing with deadlines. Discrete Appl. Math. 3 (1981) 313–318. | DOI | Zbl

and ,Approximation schemes for the restricted shortest path problem. Math. Oper. Res. 17 (1992) 36–42. | DOI | MR | Zbl

,Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals. J. Combin. Optim. (2015) 30 403–412. | DOI | MR | Zbl

, and ,R.M. Karp, Reducibility among combinatorial problems. In Complexity of Computer Computations, edited by R.E. Miller and L.W. Thatcher. Plenum Press (1972) 85–104. | MR | Zbl

A functional equation and its application to resource allocation and sequencing problems. Manage. Sci. 16 (1969) 77–84. | DOI | Zbl

and ,An improved FPTAS for mobile agent routing with time constraints. J. Universal Comput. Sci. 17 (2011) 1854–1862. | MR | Zbl

, and ,Algorithms for scheduling independent tasks. J. Assoc. Comput. Mach. 23 (1976) 116–127. | DOI | MR | Zbl

,General techniques for combinatorial approximation. Oper. Res. 25 (1977) 920–936. | DOI | MR | Zbl

,Maximizing the weighted number of just-in-time jobs in several two-machine scheduling systems. J. Scheduling 15 (2012) 39–47. | DOI | MR | Zbl

and ,Various optimizers for single-stage production. Nav. Res. Logist. Quart. 3 (1956) 59–66. | DOI | MR

,Approximation of Pareto optima in multiple objective, shortest path problems. Oper. Res. 35 (1987) 70–79. | DOI | MR | Zbl

,*Cited by Sources: *