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 (56)

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

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