Scheduling jobs with fixed start and end times

DOI10.1016/0166-218X(87)90037-0MaRDI QIDQ1098765zbMATH OpenFDO

Authors Esther M. Arkin, Ellen B. Silverberg

Publication date 1987

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

shortest pathsgraph coloringinterval graphscliqueNP-completeidentical machinesperfect graphsfixed start and end time

Mathematics Subject Classification ID

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

Recommendations

• On-line scheduling of jobs with fixed start and end times
• The k-track assignment problem
• Interval scheduling on identical machines
• scientific article; zbMATH DE number 15416
• The Fixed Job Schedule Problem with Working-Time Constraints

Cites work

• scientific article; zbMATH DE number 3644821 (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 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• A note on two problems in connexion with graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• Node-and edge-deletion NP-complete problems
• On chain and antichain families of a partially ordered set
• The node-deletion problem for hereditary properties is NP-complete
• The structure of Sperner k-families
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(87)

• Routing trains through railway stations: Complexity issues
• Compact integer linear programming formulations for the temporal bin packing problem with fire-ups
• Maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times
• On the computational complexity of (maximum) shift class scheduling
• The just-in-time scheduling problem in a flow-shop scheduling system
• A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
• Characterizing sets of jobs that admit optimal greedy-like algorithms
• Scheduling split intervals with non-uniform demands
• “Rent-or-Buy” Scheduling and Cost Coloring Problems
• Interval scheduling on identical machines
• On universally easy classes for NP-complete problems.
• Interval scheduling with economies of scale
• On the parameterized complexity of interval scheduling with eligible machine sets
• Interval scheduling on related machines
• Matching supply and demand in a sharing economy: classification, computational complexity, and application
• A fixed job scheduling problem with machine-dependent job weights
• On the tractability of satellite range scheduling
• On a variant of Flory model
• Online C-benevolent job scheduling on multiple machines
• Algorithms for large scale shift minimisation personnel task scheduling problems
• Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey
• An integrated dispatching model for rail yards operations.
• A classification scheme for integrated staff rostering and scheduling problems
• Online interval scheduling to maximize total satisfaction
• Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times
• Parameterized complexity of machine scheduling: 15 open problems
• Toward a model for backtracking and dynamic programming
• On-line scheduling of jobs with fixed start and end times
• A simple optimal algorithm for scheduling variable-sized requests
• A stronger model of dynamic programming algorithms
• Dynamic algorithms for multimachine interval scheduling through analysis of idle intervals
• Improving LTL truck load utilization on line
• Competitive algorithms for multistage online scheduling
• Pre-processing techniques for resource allocation in the heterogeneous case
• Bicriteria scheduling for contiguous and non contiguous parallel tasks
• On the \(k\)-coloring of intervals
• Scheduling with target start times
• scientific article; zbMATH DE number 7278054 (Why is no real title available?)
• Scheduling jobs within time windows on identical parallel machines: New model and algorithms
• Scheduling two jobs with fixed and nonfixed routes
• Approximating interval selection on unrelated machines with unit-length intervals and cores
• Distributionally robust fixed interval scheduling on parallel identical machines under uncertain finishing times
• Resource allocation in bounded degree trees
• AFSCN scheduling: how the problem and solution have evolved
• New partitioning techniques and faster algorithms for approximate interval scheduling
• Analysis of a parallel machine scheduling problem with sequence dependent setup times and job availability intervals
• Increasing the revenue of self-storage warehouses by optimizing order scheduling
• An analysis of shift class design problems
• Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems
• A graph colouring model for assigning a heterogeneous workforce to a given schedule
• Two-machine interval shop scheduling with time lags
• Pricing and scheduling decisions with leadtime flexibility
• Hybrid differential evolution optimisation for Earth observation satellite scheduling with time-dependent earliness-tardiness penalties
• A constraint-based approach for the shift design personnel task scheduling problem with equity
• Optimal interval scheduling with a resource constraint
• An iterative dynamic programming approach for the temporal knapsack problem
• On the complexity of interval scheduling with a resource constraint
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• A combinatorial flow-based formulation for temporal bin packing problems
• Resource allocation with time intervals
• Scheduling jobs with release times on a machine with finite storage
• The k-track assignment problem
• On the parameterized tractability of the just-in-time flow-shop scheduling problem
• On the computational complexity of (maximum) class scheduling
• Multistage interval scheduling games
• The k-Track assignment problem on partial orders
• Just-in-time scheduling with controllable processing times on parallel machines
• Maximizing the weighted number of just‐in‐time jobs in a distributed flow‐shop scheduling system
• Exact and approximation algorithms for the operational fixed interval scheduling problem
• Decomposition algorithms for the interval scheduling problem
• Fast primal-dual distributed algorithms for scheduling and matching problems
• License class design: Complexity and algorithms
• Minimum loss scheduling problems
• Improved algorithms for scheduling unsplittable flows on paths
• Sharing video on demand
• Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups
• Maximizing the value of a space mission
• Mobility offer allocations in corporate settings
• Cost constrained fixed job scheduling.
• Online interval scheduling with a bounded number of failures
• Inverse interval scheduling via reduction on a single machine
• Efficient job scheduling algorithms with multi-type contentions
• Runway sequencing with holding patterns
• The optimal cost chromatic partition problem for trees and interval graphs
• Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation
• Interval scheduling maximizing minimum coverage

This page was built for publication: Scheduling jobs with fixed start and end times

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