A Combinatorial Approximation Algorithm for the Vector Scheduling with Submodular Penalties on Parallel Machines

A Combinatorial Approximation Algorithm for the Vector Scheduling with Submodular Penalties on Parallel Machines

In this paper, we focus on solving the vector scheduling problem with submodular penalties on parallel machines. We are given n jobs and m parallel machines, where each job is associated with a d-dimensional vector. Each job can either be rejected, incurring a rejection penalty, or accepted and proc...

书目详细资料
Main Authors:	Bihui Cheng, Wencheng Wang
格式:	文件
语言:	English
出版:	Hindawi Limited 2023-01-01
丛编:	Journal of Mathematics
在线阅读:	http://dx.doi.org/10.1155/2023/8886388

相似书籍

A Combinatorial 2-Approximation Algorithm for the Parallel-Machine Scheduling with Release Times and Submodular Penalties
由: Wencheng Wang, et al.
出版: (2021-12-01)

Approximation Algorithms for the Submodular Load Balancing with Submodular Penalties
由: Xiaofei Liu, et al.
出版: (2020-10-01)

Approximation Algorithm for the Single Machine Scheduling Problem with Release Dates and Submodular Rejection Penalty
由: Xiaofei Liu, et al.
出版: (2020-01-01)

An Improved Approximation Algorithm for the Minimum Power Cover Problem with Submodular Penalty
由: Han Dai
出版: (2022-10-01)

A simple combinatorial algorithm for submodular function minimization
由: Iwata, Satoru, et al.
出版: (2011)

Costly circuits, submodular schedules and approximate Carathéodory Theorems
由: Bojja Venkatakrishnan, Shaileshh, et al.
出版: (2018)

Approximating Submodular Functions Everywhere
由: Goemans, Michel X., et al.
出版: (2011)

Single Machine Vector Scheduling with General Penalties
由: Xiaofei Liu, et al.
出版: (2021-08-01)

Hardness and approximation of submodular minimum linear ordering problems
由: Farhadi, Majid, et al.
出版: (2023)

Optimizing Penalties of Total Lateness and Energy Costs for Heterogeneous Parallel Machines Scheduling Using Memetic Algorithm
由: Javad Behnamian, et al.
出版: (2020-09-01)

Scheduling to Minimize Power Consumption using Submodular Functions
由: Demaine, Erik D., et al.
出版: (2012)

Scheduling to minimize power consumption using submodular functions
由: Zadimoghaddam, Morteza
出版: (2011)

Improved Combinatorial Benders Decomposition for a Scheduling Problem with Unrelated Parallel Machines
由: Francisco Regis Abreu Gomes, et al.
出版: (2017-01-01)

Two Combinatorial Algorithms for the Constrained Assignment Problem with Bounds and Penalties
由: Guojun Hu, et al.
出版: (2023-12-01)

Approximation Algorithms and an FPTAS for the Single Machine Problem with Biased Tardiness Penalty
由: G. Moslehi, et al.
出版: (2014-01-01)

Single-machine scheduling for minimizing earliness and tardiness penalties by genetic algorithms
由: Imran Ah Chaudhry, et al.
出版: (2014-01-01)

Which submodular functions are expressible using binary submodular functions?
由: Živný, S, et al.
出版: (2008)

Which submodular functions are expressible using binary submodular functions?
由: Živný, S, et al.
出版: (2008)

Analysis of an Approximation Algorithm for Scheduling Independent Parallel Tasks
由: Keqin Li
出版: (1999-01-01)

Analysis of an Approximation Algorithm for Scheduling Independent Parallel Tasks
由: Keqin Li
出版: (1999-12-01)

Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-based Approximation Algorithms
由: Murray, Riley, et al.
出版: (2018)

Corrigendum to “Improved Combinatorial Benders Decomposition for a Scheduling Problem with Unrelated Parallel Machines”
由: Francisco Regis Abreu Gomes, et al.
出版: (2017-01-01)

Discrete Newton’s Algorithm for Parametric Submodular Function Minimization
由: Goemans, Michel X, et al.
出版: (2018)

Approximation algorithms for stochastic scheduling on unrelated machines
由: Scott, Jacob (Jacob Healy)
出版: (2009)

Algorithms and approximation schemes for machine scheduling problems
由: Sengupta, Sudipta, 1974-
出版: (2013)

Parallel parametric combinatorial search : its application to runway scheduling
由: Trivizas, Dionyssios Anastasios
出版: (2012)

Stochastic Block-Coordinate Gradient Projection Algorithms for Submodular Maximization
由: Zhigang Li, et al.
出版: (2018-01-01)

Some Algorithms Used in Parallel Machine Scheduling
由: Adel Alhajjar, et al.
出版: (2023-06-01)

The submodular joint replenishment problem
由: Cheung, Maurice, et al.
出版: (2015)

Submodular Secretary Problem and Extensions
由: Zadimoghaddam, Morteza, et al.
出版: (2010)

Distributionally robust submodular maximization
由: Staib, Matthew, et al.
出版: (2021)

Matchings, matroids and submodular functions
由: Harvey, Nicholas James Alexander
出版: (2009)

Approximation algorithms for combinatorial optimization under uncertainty
由: Minkoff, Maria, 1976-
出版: (2014)

Minimizing a General Penalty Function on a Single Machine via Developing Approximation Algorithms and FPTASs
由: Kamran Kianfar, et al.
出版: (2017-09-01)

Support Vector Machines in Combinatorial Chemistry
由: Matthew W B Trotter, et al.
出版: (2001-10-01)

Parallel genetic algorithms on combinatorial optimization problems
由: Francisco Hidrobo, et al.
出版: (2011-01-01)

Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations
由: Goemans, Michel X., et al.
出版: (2013)

An Asymptotically Optimal On-Line Algorithm for Parallel Machine Scheduling
由: Chou, Mabel, et al.
出版: (2003)

IDENTICAL PARALLEL MACHINES SCHEDULING USING GENETIC ALGORITHM
由: Aseel J Haleel
出版: (2018-08-01)

Tight approximation bounds for combinatorial frugal coverage algorithms
由: Caragiannis, I, et al.
出版: (2013)