Scheduling jobs with fixed start and end times

DOI10.1016/0166-218X(87)90037-0zbMATH Open0636.90042MaRDI QIDQ1098765FDOQ1098765

Authors: Esther M. Arkin, Ellen B. Silverberg 

Publication date: 1987

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

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

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)

Cites Work

• A note on two problems in connexion with graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fibonacci heaps and their uses in improved network optimization algorithms
• Title not available (Why is that?)
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• The node-deletion problem for hereditary properties is NP-complete
• Title not available (Why is that?)
• Node-and edge-deletion NP-complete problems
• On chain and antichain families of a partially ordered set
• The structure of Sperner k-families

Cited In (87)

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

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)