Fixed interval scheduling: models, applications, computational complexity and algorithms

DOI10.1016/J.EJOR.2006.01.049MaRDI QIDQ859906zbMATHOpenAlexFDO

Authors N. E. Zubov

Publication date 22 January 2007

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2006.01.049

zbMATH Keywords

maximum weight independent setinterval graph\(k\)-coloringmaximum weight clique\(k\)-track assignmentbinterval schedulingdiscrete starting times

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Graph algorithms (graph-theoretic aspects) (05C85) Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Exact and approximation algorithms for the operational fixed interval scheduling problem
• Exact and Approximation Algorithms for the Tactical Fixed Interval Scheduling Problem
• The \(k\)-track assignment problem
• Scheduling jobs with fixed start and end times
• Interval scheduling on identical machines

Cites work

• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 1003261 (Why is no real title available?)
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 1961993 (Why is no real title available?)
• scientific article; zbMATH DE number 2038752 (Why is no real title available?)
• scientific article; zbMATH DE number 2038779 (Why is no real title available?)
• scientific article; zbMATH DE number 2079894 (Why is no real title available?)
• scientific article; zbMATH DE number 2080249 (Why is no real title available?)
• scientific article; zbMATH DE number 863504 (Why is no real title available?)
• scientific article; zbMATH DE number 956839 (Why is no real title available?)
• A Greedy On-Line Algorithm for thek-Track Assignment Problem
• A branch and bound algorithm for the maximum clique problem
• A branch-and-price algorithm for a hierarchical crew scheduling problem
• A fast algorithm for the maximum weight clique problem
• A generalization of chordal graphs and the maximum clique problem
• A heuristic approach to the bus driver scheduling problem
• A note on the maximum number of on-time jobs on parallel identical machines.
• A primal-dual interior point method whose running time depends only on the constraint matrix
• A sequential algorithm for finding a maximum weightK-independent set on interval graphs
• A simple optimal algorithm for scheduling variable-sized requests
• A unified analysis of paging and caching
• A unified approach to approximating resource allocation and scheduling
• Aligning two fragmented sequences
• An Optimal Solution for the Channel-Assignment Problem
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• An improved randomized on-line algorithm for a weighted interval selection problem
• Approximating the throughput of multiple machines in real-time scheduling
• Approximation Algorithms for Fixed Job Schedule Problems
• Approximation algorithms for NMR spectral peak assignment.
• Bounding the Power of Preemption in Randomized Scheduling
• Continuous Characterizations of the Maximum Clique Problem
• Convergence rate of the gradient descent method with dilatation of the space
• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• Dual quadratic estimates in polynomial and Boolean programming
• Early/tardy scheduling with sequence dependent setups on uniform parallel machines
• Exact and Approximation Algorithms for the Tactical Fixed Interval Scheduling Problem
• Exploiting sparsity in primal-dual interior-point methods for semidefinite programming
• Games of Boldness, Where the Player Performing the Hardest Task Wins
• Geometric algorithms and combinatorial optimization.
• Global escape strategies for maximizing quadratic forms over a simplex
• Interval scheduling on identical machines
• Interval selection: Applications, algorithms, and lower bounds
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Maximum \(k\)-covering of weighted transitive graphs with applications
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Maximum weightk-independent set problem on permutation graphs
• Minimal Resources for Fixed and Variable Job Schedules
• Minimizing the sum of job earliness and tardiness in a multimachine system
• More reliable protein NMR peak assignment via improved 2-interval scheduling
• Network flows. Theory, algorithms, and applications.
• Note on scheduling intervals on-line
• On chain and antichain families of a partially ordered set
• On standard quadratic optimization problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the Maximum Weight Clique Problem
• On the \(k\)-coloring of intervals
• On the approximability of an interval scheduling problem
• On the complexity of scheduling tasks with discrete starting times
• On the computational complexity of (maximum) class scheduling
• On the power of randomization in on-line algorithms
• On-line scheduling of jobs with fixed start and end times
• Parallel machine scheduling with earliness and tardiness penalties
• Periodic assignment and graph colouring
• Polyhedral proof methods in combinatorial optimization
• Progress on perfect graphs
• Properties of vertex packing and independence system polyhedra
• Randomized online interval scheduling
• Reactive local search for the maximum clique problem
• Real time scheduling theory: A historical perspective
• Recognizing Berge graphs
• Scheduling jobs with fixed start and end times
• Scheduling jobs within time windows on identical parallel machines: New model and algorithms
• Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs
• The Complexity of Coloring Circular Arcs and Chords
• The \(k\)-track assignment problem
• The combinatorics of pivoting for the maximum weight clique.
• The ellipsoid method and its consequences in combinatorial optimization
• The maximum k-colorable subgraph problem for chordal graphs
• The relation of time indexed formulations of single machine scheduling problems to the node packing problem
• The seat reservation problem
• The strong perfect graph theorem
• Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem
• Vertex packings: Structural properties and algorithms
• When Is the Classroom Assignment Problem Hard?

Cited in

(70)

• An improved online algorithm for the online preemptive scheduling of equal-length intervals on a single machine with lookahead
• Interval scheduling on related machines
• A state-of-the-art survey on multi-scenario scheduling
• Improved randomized results for the interval selection problem
• Scheduling batches in flowshop with limited buffers in the shampoo industry
• Multi-agent scheduling in a no-wait flow shop system to maximize the weighted number of just-in-time jobs
• A triplet-based exact method for the shift minimisation personnel task scheduling problem
• Scheduling and fixed-parameter tractability
• Real-time scheduling to minimize machine busy times
• Improved Randomized Results for That Interval Selection Problem
• Working time constraints in operational fixed job scheduling
• On the parameterized tractability of the just-in-time flow-shop scheduling problem
• A Novel Approximate Algorithm for Admission Control
• Two-agent single machine scheduling with forbidden intervals
• Distributionally robust fixed interval scheduling on parallel identical machines under uncertain finishing times
• On the complexity of adjacent resource scheduling
• A fixed job scheduling problem with machine-dependent job weights
• Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey
• The \(k\)-track assignment problem
• Multistage interval scheduling games
• Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem
• Interval scheduling with economies of scale
• Just-in-time scheduling with controllable processing times on parallel machines
• Interval selection with machine-dependent intervals
• Flow-based formulations for operational fixed interval scheduling problems with random delays
• Fixed interval scheduling with third‐party machines
• Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs
• Minimizing total busy time in parallel scheduling with application to optical networks
• On the complexity of interval scheduling with a resource constraint
• Online optimization of busy time on parallel machines. (Extended abstract)
• Vyacheslav Tanaev: contributions to scheduling and related areas
• Dynamic algorithms for multimachine interval scheduling through analysis of idle intervals
• The just-in-time scheduling problem in a flow-shop scheduling system
• Dynamising Interval Scheduling: The Monotonic Case
• Online interval scheduling with a bounded number of failures
• Operational fixed job scheduling problem under spread time constraints: a branch-and-price algorithm
• Models and algorithms for energy-efficient scheduling with immediate start of jobs
• A survey on scheduling problems with due windows
• Inverse interval scheduling via reduction on a single machine
• Improving fleet utilization for carriers by interval scheduling
• Scheduling preparation of doses for a chemotherapy service
• Online C-benevolent job scheduling on multiple machines
• Multi-agent scheduling on a single machine with max-form criteria
• Increasing the revenue of self-storage warehouses by optimizing order scheduling
• Dynamic node packing
• Online interval scheduling to maximize total satisfaction
• Interval scheduling maximizing minimum coverage
• Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
• Optimal interval scheduling with a resource constraint
• Tactical fixed job scheduling with spread-time constraints
• On the tractability of satellite range scheduling
• Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems
• Online interval scheduling on a single machine with finite lookahead
• Interval scheduling: A survey
• Optimization of template-driven scheduling mechanisms: Regularity measures and computational techniques
• Exact and approximation algorithms for the operational fixed interval scheduling problem
• Optimizing busy time on parallel machines
• Online optimization of busy time on parallel machines
• Primal-dual analysis for online interval scheduling problems
• Multithread interval scheduling with flexible machine availabilities: complexity and efficient algorithms
• Minimizing grid capacity in preemptive electric vehicle charging orchestration: complexity, exact and heuristic approaches
• Scheduling two interfering job sets on identical parallel machines with makespan and total completion time minimization
• Mobility offer allocations in corporate settings
• A Lagrangian relaxation algorithm for stochastic fixed interval scheduling problem with non-identical machines and job classes
• Any-order online interval selection
• Approximating interval selection on unrelated machines with unit-length intervals and cores
• Multi-depot electric vehicle scheduling in in-plant production logistics considering non-linear charging models
• Decomposition algorithms for the interval scheduling problem
• On the parameterized complexity of interval scheduling with eligible machine sets
• Optimal scheduling with nested time intervals and three-dimensional strip packing on comparability graphs of an arborescence order

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: Fixed interval scheduling: models, applications, computational complexity and algorithms

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