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

DOI10.1016/J.EJOR.2006.01.049zbMATH Open1107.90019OpenAlexW2051158805MaRDI QIDQ859906FDOQ859906

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)

Cites Work

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

Cited In (66)

• Dynamic node packing
• Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs
• The just-in-time scheduling problem in a flow-shop scheduling system
• Improving fleet utilization for carriers by interval scheduling
• A Novel Approximate Algorithm for Admission Control
• Interval scheduling with economies of scale
• An improved online algorithm for the online preemptive scheduling of equal-length intervals on a single machine with lookahead
• Interval scheduling on related machines
• Working time constraints in operational fixed job scheduling
• A fixed job scheduling problem with machine-dependent job weights
• Dynamising Interval Scheduling: The Monotonic Case
• Online Optimization of Busy Time on Parallel Machines
• Operational fixed job scheduling problem under spread time constraints: a branch-and-price algorithm
• On the tractability of satellite range scheduling
• Online C-benevolent job scheduling on multiple machines
• Improved randomized results for the interval selection problem
• Real-time scheduling to minimize machine busy times
• Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey
• Online interval scheduling to maximize total satisfaction
• Improved Randomized Results for That Interval Selection Problem
• Optimization of template-driven scheduling mechanisms: Regularity measures and computational techniques
• A Triplet-Based Exact Method for the Shift Minimisation Personnel Task Scheduling Problem
• Multi-agent scheduling in a no-wait flow shop system to maximize the weighted number of just-in-time jobs
• Dynamic algorithms for multimachine interval scheduling through analysis of idle intervals
• Fixed interval scheduling with third‐party machines
• Distributionally robust fixed interval scheduling on parallel identical machines under uncertain finishing times
• Flow-based formulations for operational fixed interval scheduling problems with random delays
• Scheduling preparation of doses for a chemotherapy service
• Increasing the revenue of self-storage warehouses by optimizing order scheduling
• Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems
• A state-of-the-art survey on multi-scenario scheduling
• 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
• Online interval scheduling on a single machine with finite lookahead
• Optimizing busy time on parallel machines
• Online optimization of busy time on parallel machines
• Two-agent single machine scheduling with forbidden intervals
• On the complexity of interval scheduling with a resource constraint
• Multi-agent scheduling on a single machine with max-form criteria
• Scheduling and fixed-parameter tractability
• On the parameterized tractability of the just-in-time flow-shop scheduling problem
• The \(k\)-track assignment problem
• Minimizing total busy time in parallel scheduling with application to optical networks
• A survey on scheduling problems with due windows
• Multistage interval scheduling games
• Just-in-time scheduling with controllable processing times on parallel machines
• Exact and approximation algorithms for the operational fixed interval scheduling problem
• Primal-dual analysis for online interval scheduling problems
• Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem
• Vyacheslav Tanaev: contributions to scheduling and related areas
• Online interval scheduling with a bounded number of failures
• Inverse interval scheduling via reduction on a single machine
• Scheduling batches in flowshop with limited buffers in the shampoo industry
• Models and algorithms for energy-efficient scheduling with immediate start of jobs
• Interval scheduling maximizing minimum coverage
• DECOMPOSITION ALGORITHMS FOR THE INTERVAL SCHEDULING PROBLEM
• On the parameterized complexity of interval scheduling with eligible machine sets
• Any-order online interval selection
• 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
• Approximating Interval Selection on Unrelated Machines with Unit-Length Intervals and Cores
• Scheduling two interfering job sets on identical parallel machines with makespan and total completion time minimization
• Multi-depot electric vehicle scheduling in in-plant production logistics considering non-linear charging models
• Mobility offer allocations in corporate settings
• A Lagrangian relaxation algorithm for stochastic fixed interval scheduling problem with non-identical machines and job classes

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)