Ten notes on equal-processing-time scheduling: at the frontiers of solvability in polynomial time

DOI10.1007/S10288-003-0024-4zbMATH Open1070.90041OpenAlexW1704392916MaRDI QIDQ1885337FDOQ1885337

Authors: Philippe Baptiste, Peter Brucker, Sigrid Knust, Vadim G. Timkovsky 

Publication date: 28 October 2004

Published in: 4OR (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10288-003-0024-4

Recommendations

• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Preemptive scheduling of equal-length jobs in polynomial time
• On polynomial solvability of two multiprocessor scheduling problems
• A polynomial time approximation scheme for general multiprocessor job scheduling (extended abstract)
• Variants of Multi-resource Scheduling Problems with Equal Processing Times
• On PreemptiveResource Constrained Scheduling: Polynomial-Time Approximation Schemes
• scientific article; zbMATH DE number 2086932
• On the optimality of exact and approximation algorithms for scheduling problems
• Multiprocessor scheduling under precedence constraints: polyhedral results
• On a parallel machine scheduling problem with equal processing times

zbMATH Keywords

computational complexityschedulingpolynomial time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Cited In (32)

• New complexity results for parallel identical machine scheduling problems with preemption, release dates and regular criteria
• Preemptive scheduling of equal-length jobs to maximize weighted throughput.
• A new polynomial algorithm for a parallel identical scheduling problem
• Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs
• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• On maximizing the profit of a satellite launcher: selecting and scheduling tasks with time windows and setups
• Scheduling unit time jobs with integer release dates to minimize the weighted number of tardy jobs
• Parameterized complexity of machine scheduling: 15 open problems
• Time-of-use scheduling problem with equal-length jobs
• Branch less, cut more and minimize the number of late equal-length jobs on identical machines
• Preemptive scheduling of two uniform parallel machines to minimize total tardiness
• A decomposition scheme for single stage scheduling problems
• Three notes on scheduling unit-length jobs with precedence constraints to minimize the total completion time
• Ideal schedules in parallel machine settings
• Scheduling jobs with release dates on parallel batch processing machines
• The \(m\)-machine flowshop problem with unit-time operations and intree precedence constraints
• Integer preemptive scheduling on parallel machines
• On a parallel machine scheduling problem with equal processing times
• Parallel machine problems with equal processing times: a survey
• Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines
• A survey of single machine scheduling to minimize weighted number of tardy jobs
• A complexity analysis of parallel scheduling unit-time jobs with in-tree precedence constraints while minimizing the mean flow time
• Approximations for Throughput Maximization
• Integrality Property in Preemptive Parallel Machine Scheduling
• Scheduling problem with multi-purpose parallel machines
• A note on batch scheduling on a two-machine flowshop with machine-dependent processing times
• Equitable scheduling on a single machine
• Normal-form preemption sequences for an open problem in scheduling theory
• On the optimality of the earliest due date rule in stochastic scheduling and in queueing
• Minimizing the weighted number of tardy jobs on multiple machines: a review
• Title not available (Why is that?)
• Scheduling equal length jobs with eligibility restrictions

This page was built for publication: Ten notes on equal-processing-time scheduling: at the frontiers of solvability in polynomial time

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