Fast approximation algorithms for job scheduling with processing set restrictions

DOI10.1016/J.TCS.2010.08.008MaRDI QIDQ410716zbMATH OpenOpenAlexFDO

Authors Yumei Huo, Joseph Y.-T. Leung

Publication date 3 April 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.08.008

zbMATH Keywords

NP-hardinclusive processing setmakespan minimizationnested processing setnonpreemptive schedulingpolynomial-time approximation algorithmtree-hierarchical processing set

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Parallel machine scheduling with nested processing set restrictions
• Fast approximation algorithms for uniform machine scheduling with processing set restrictions
• Parallel machine scheduling with job assignment restrictions
• Parallel batch scheduling with nested processing set restrictions
• Preemptive scheduling algorithms with nested processing set restriction

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1302193 (Why is no real title available?)
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Approximation algorithms for scheduling unrelated parallel machines
• On-line load balancing in a hierarchical server topology
• Parallel machine scheduling under a grade of service provision
• Parallel machine scheduling with job assignment restrictions
• Parallel machine scheduling with nested job assignment restrictions
• Parallel machine scheduling with nested processing set restrictions
• Scheduling parallel machines with inclusive processing set restrictions
• Scheduling parallel machines with inclusive processing set restrictions and job release times
• Scheduling unit length jobs with parallel nested machine processing set restrictions
• Task Scheduling on a Multiprocessor System with Independent Memories

Cited in

(20)

• On some special cases of the restricted assignment problem
• Mixed coordination mechanisms for scheduling games on hierarchical machines
• Makespan minimization in online scheduling with machine eligibility
• Multiple subset sum with inclusive assignment set restrictions
• Fast approximation algorithms for uniform machine scheduling with processing set restrictions
• Heuristics for online scheduling on identical parallel machines with two GoS levels
• Effective heuristics for makespan minimization in parallel batch machines with non-identical capacities and job release times
• A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions
• Scheduling jobs with release and delivery times subject to nested eligibility constraints
• Scheduling uniform machines with restricted assignment
• Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs
• Scheduling with tree-hierarchical processing set restrictions
• Parallel batch scheduling with nested processing set restrictions
• Parallel machine scheduling with job assignment restrictions
• Preemptive scheduling algorithms with nested processing set restriction
• Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan
• Parallel machine scheduling with nested processing set restrictions and job delivery times
• Makespan minimization in online scheduling with machine eligibility
• Approximation algorithms for batch scheduling with processing set restrictions
• Scheduling partially ordered jobs faster than \(2^n\)

This page was built for publication: Fast approximation algorithms for job scheduling with processing set restrictions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q410716)