nach oben

Journal of Combinatorial Optimization

Erschienen in:

04.01.2022

Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties

verfasst von: Hongye Zheng, Suogang Gao, Wen Liu, Weili Wu, Ding-Zhu Du, Bo Hou

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2022

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we consider the parallel-machine scheduling problem with release dates and submodular rejection penalties. In this problem, we are given m identical parallel machines and n jobs. Each job has a processing time and a release date. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on one of the m identical parallel machines. The objective is to minimize the sum of the makespan of the accepted jobs and the rejection penalty of the rejected jobs which is determined by a submodular function. Our main work is to design a 2-approximation algorithm based on the primal-dual framework.

Vorheriger Artikel The effect of vertex and edge deletion on the edge metric dimension of graphs

Nächster Artikel Joint chance-constrained staffing optimization in multi-skill call centers

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Bartal Y, Leonardi S, Marchetti-Spaccamela A, Sgall JSL (2000) Multiprocessor scheduling with rejection. SIAM J Discrete Math 13:64–78MathSciNetCrossRef

Chenier C, Urrutia J, Zaguia N (1995) Scheduling tasks with communication delays on parallel processors. Order 12(3):213–220MathSciNetCrossRef

Fleicher L, Iwata S (2003) A push-relabel framework for submodular function minimization and applications to parametric optimization. Discrete Appl Math 131:311–322MathSciNetCrossRef

Fujishige S (2005) Submodular functions and optimization, 2nd edn. Elsevier, AmsterdamMATH

Graham RL (1966) Bounds for certain multiprocessing anomalies. Bell Syst Tech J 45(9):1563–1581CrossRef

Iwata S, Fleischer L, Fujishige S (2001) A combinatorial strongly polynomial algorithm for minimizing submodular finction. J ACM 48:761–777MathSciNetCrossRef

Lawler EL (1973) Optimal sequencing a single machine subject to precedence constraints. Manag Sci 19:544–546CrossRef

Leutenegger ST, Vernon MK (1990) The performance of multiprogrammed multiprocessor scheduling algorithms. In: Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, pp 226–236

Liu X, Li W (2020) Approximation algorithm for the single machine scheduling problem with release dates and submodular rejection penalty. Mathematics 8:133CrossRef

Liu X, Li W (2021) Approximation algorithms for the multiprocessor scheduling with submodular penalties. Optim Lett. https://doi.org/10.1007/s11590-021-01724-1MathSciNetCrossRefMATH

Lovász L (1983) Submodular functions and convexity. In: Bachm A, Grtschel M, Korte B (eds) Mathematical programing the state of the art. Springer, Berlin, pp 235–237

Shabtay D, Gaspar N, Kaspi M (2013) A survey on offline scheduling with rejection. J Sched 16:3–28MathSciNetCrossRef

Sotskov YN, Egorova NG (2019) The optimality region for a single-machine scheduling problem with bounded durations of the jobs and the total completion time objective. Mathematics 7:382CrossRef

Xu D, Wang F, Du D, Wu C (2016) Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique. Theor Comput Sci 630:117–125MathSciNetCrossRef

Zhang L, Lu L (2016) Parallel-machine scheduling with release dates and rejection. 4OR 14:165–172MathSciNetCrossRef

Zhang X, Xu D, Du D, Wu C (2018) Approximation algorithms for precedence-constrained identical machine scheduling with rejection. J Comb Optim 35(1):318–330MathSciNetCrossRef

Zhong X, Pan Z, Jiang D (2017) Scheduling with release times and rejection on two parallel machines. J Comb Optim 33(3):934–944MathSciNetCrossRef

Titel: Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties
verfasst von: Hongye Zheng
Suogang Gao
Wen Liu
Weili Wu
Ding-Zhu Du
Bo Hou
Publikationsdatum: 04.01.2022
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2022
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-021-00842-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2022

Single-machine multitasking scheduling with job efficiency promotion

An efficient spread-based evolutionary algorithm for solving dynamic multi-objective optimization problems

The signed edge-domatic number of nearly cubic graphs

Multi-objective multi-verse optimiser for integrated two-sided assembly sequence planning and line balancing

A variable neighborhood search algorithm for human resource selection and optimization problem in the home appliance manufacturing industry

The sum of root-leaf distance interdiction problem by upgrading edges/nodes on trees

Premium Partner