Scheduling jobs with fixed start and end times
From MaRDI portal
Publication:1098765
DOI10.1016/0166-218X(87)90037-0zbMath0636.90042MaRDI QIDQ1098765
Ellen B. Silverberg, Esther M. Arkin
Publication date: 1987
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
graph coloringshortest pathsperfect graphscliqueNP-completeinterval graphsidentical machinesfixed start and end time
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)
Related Items
A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs ⋮ Scheduling jobs with release times on a machine with finite storage ⋮ On-line scheduling of jobs with fixed start and end times ⋮ A simple optimal algorithm for scheduling variable-sized requests ⋮ Maximizing the value of a space mission ⋮ An analysis of shift class design problems ⋮ Fast primal-dual distributed algorithms for scheduling and matching problems ⋮ On the \(k\)-coloring of intervals ⋮ 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 ⋮ A fixed job scheduling problem with machine-dependent job weights ⋮ A constraint-based approach for the shift design personnel task scheduling problem with equity ⋮ Optimal interval scheduling with a resource constraint ⋮ Distributionally robust fixed interval scheduling on parallel identical machines under uncertain finishing times ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ Inverse interval scheduling via reduction on a single machine ⋮ Resource allocation with time intervals ⋮ Compact integer linear programming formulations for the temporal bin packing problem with fire-ups ⋮ Scheduling jobs within time windows on identical parallel machines: New model and algorithms ⋮ Exact and approximation algorithms for the operational fixed interval scheduling problem ⋮ Maximizing the weighted number of just-in-time jobs on a single machine with position-dependent processing times ⋮ Maximizing the weighted number of just‐in‐time jobs in a distributed flow‐shop scheduling system ⋮ Two-machine interval shop scheduling with time lags ⋮ Sharing video on demand ⋮ A combinatorial flow-based formulation for temporal bin packing problems ⋮ Mobility offer allocations in corporate settings ⋮ Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey ⋮ On universally easy classes for NP-complete problems. ⋮ Improved algorithms for scheduling unsplittable flows on paths ⋮ The just-in-time scheduling problem in a flow-shop scheduling system ⋮ Toward a model for backtracking and dynamic programming ⋮ Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems ⋮ Algorithms for large scale shift minimisation personnel task scheduling problems ⋮ Online interval scheduling with a bounded number of failures ⋮ An integrated dispatching model for rail yards operations. ⋮ Scheduling split intervals with non-uniform demands ⋮ On the computational complexity of (maximum) class scheduling ⋮ Bicriteria scheduling for contiguous and non contiguous parallel tasks ⋮ The \(k\)-Track assignment problem on partial orders ⋮ Online C-benevolent job scheduling on multiple machines ⋮ AFSCN scheduling: how the problem and solution have evolved ⋮ Hybrid differential evolution optimisation for Earth observation satellite scheduling with time-dependent earliness-tardiness penalties ⋮ On the computational complexity of (maximum) shift class scheduling ⋮ Minimum loss scheduling problems ⋮ Competitive algorithms for multistage online scheduling ⋮ Matching supply and demand in a sharing economy: classification, computational complexity, and application ⋮ Interval scheduling maximizing minimum coverage ⋮ Improving LTL truck load utilization on line ⋮ Characterizing sets of jobs that admit optimal greedy-like algorithms ⋮ Runway sequencing with holding patterns ⋮ License class design: Complexity and algorithms ⋮ Interval scheduling on related machines ⋮ A stronger model of dynamic programming algorithms ⋮ On the complexity of interval scheduling with a resource constraint ⋮ Just-in-time scheduling with controllable processing times on parallel machines ⋮ On the tractability of satellite range scheduling ⋮ DECOMPOSITION ALGORITHMS FOR THE INTERVAL SCHEDULING PROBLEM ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ An iterative dynamic programming approach for the temporal knapsack problem ⋮ Multistage interval scheduling games ⋮ Dynamic algorithms for multimachine interval scheduling through analysis of idle intervals ⋮ Online interval scheduling to maximize total satisfaction ⋮ Solving the temporal knapsack problem via recursive Dantzig-Wolfe reformulation ⋮ “Rent-or-Buy” Scheduling and Cost Coloring Problems ⋮ On the parameterized tractability of the just-in-time flow-shop scheduling problem ⋮ A graph colouring model for assigning a heterogeneous workforce to a given schedule ⋮ Resource allocation in bounded degree trees ⋮ Routing trains through railway stations: Complexity issues ⋮ Unnamed Item ⋮ Approximating Interval Selection on Unrelated Machines with Unit-Length Intervals and Cores ⋮ Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups ⋮ Interval scheduling on identical machines ⋮ Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review ⋮ Pre-processing techniques for resource allocation in the heterogeneous case ⋮ A classification scheme for integrated staff rostering and scheduling problems ⋮ Pricing and scheduling decisions with leadtime flexibility ⋮ Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times ⋮ Interval scheduling with economies of scale ⋮ The \(k\)-track assignment problem ⋮ Efficient job scheduling algorithms with multi-type contentions
Cites Work
- A note on two problems in connexion with graphs
- The node-deletion problem for hereditary properties is NP-complete
- On chain and antichain families of a partially ordered set
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Fibonacci heaps and their uses in improved network optimization algorithms
- Node-and edge-deletion NP-complete problems
- The structure of Sperner k-families
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
