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

DOI10.1016/j.ejor.2006.01.049zbMath1107.90019OpenAlexW2051158805MaRDI QIDQ859906

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

interval graphmaximum weight independent set\(k\)-coloringmaximum weight clique\(k\)-track assignmentbinterval schedulingdiscrete starting times

Mathematics Subject Classification ID

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

Related Items

Working time constraints in operational fixed job scheduling, Online Optimization of Busy Time on Parallel Machines, A survey on scheduling problems with due windows, 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, Increasing the revenue of self-storage warehouses by optimizing order scheduling, A fixed job scheduling problem with machine-dependent job weights, Tactical fixed job scheduling with spread-time constraints, Optimal interval scheduling with a resource constraint, Distributionally robust fixed interval scheduling on parallel identical machines under uncertain finishing times, Online interval scheduling on a single machine with finite lookahead, Inverse interval scheduling via reduction on a single machine, A Novel Approximate Algorithm for Admission Control, Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs, Scheduling preparation of doses for a chemotherapy service, Primal-dual analysis for online interval scheduling problems, Fixed interval scheduling with third‐party machines, Minimizing grid capacity in preemptive electric vehicle charging orchestration: complexity, exact and heuristic approaches, Multi-depot electric vehicle scheduling in in-plant production logistics considering non-linear charging models, A state-of-the-art survey on multi-scenario scheduling, Mobility offer allocations in corporate settings, Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey, The just-in-time scheduling problem in a flow-shop scheduling system, Two-agent single machine scheduling with forbidden intervals, Real-time scheduling to minimize machine busy times, Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems, Vyacheslav Tanaev: contributions to scheduling and related areas, Improving fleet utilization for carriers by interval scheduling, Online interval scheduling with a bounded number of failures, Improved Randomized Results for That Interval Selection Problem, Optimizing busy time on parallel machines, Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem, Online optimization of busy time on parallel machines, Online C-benevolent job scheduling on multiple machines, Multi-agent scheduling on a single machine with max-form criteria, Interval scheduling maximizing minimum coverage, Scheduling batches in flowshop with limited buffers in the shampoo industry, Interval scheduling on related machines, On the complexity of interval scheduling with a resource constraint, Just-in-time scheduling with controllable processing times on parallel machines, Minimizing total busy time in parallel scheduling with application to optical networks, On the tractability of satellite range scheduling, DECOMPOSITION ALGORITHMS FOR THE INTERVAL SCHEDULING PROBLEM, Improved randomized results for the interval selection problem, Operational fixed job scheduling problem under spread time constraints: a branch-and-price algorithm, An Improved Online Algorithm for the Online Preemptive Scheduling of Equal-Length Intervals on a Single Machine with Lookahead, Flow-based formulations for operational fixed interval scheduling problems with random delays, Multistage interval scheduling games, Dynamic algorithms for multimachine interval scheduling through analysis of idle intervals, Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach, Online interval scheduling to maximize total satisfaction, On the parameterized tractability of the just-in-time flow-shop scheduling problem, Models and algorithms for energy-efficient scheduling with immediate start of jobs, Approximating Interval Selection on Unrelated Machines with Unit-Length Intervals and Cores, Dynamic node packing, Interval scheduling with economies of scale

Uses Software

• DIMACS

Cites Work

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