Approximation Algorithms for Fixed Job Schedule Problems

DOI10.1287/OPRE.40.1.S96MaRDI QIDQ3990569zbMATH OpenFDO

Authors Matteo Fischetti, Silvano Martello, Paolo Toth

Publication date 28 June 1992

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/OPRE.40.1.S96

zbMATH Keywords

fixed job schedule problemgreedy solutionpolynomial-time approximation algorithmspreemptive relaxation

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The Fixed Job Schedule Problem with Working-Time Constraints
• The Fixed Job Schedule Problem with Spread-Time Constraints
• scientific article; zbMATH DE number 1512677
• APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS
• scientific article; zbMATH DE number 1418275

Cited in

(29)

• Routing trains through railway stations: Complexity issues
• An approximation algorithm for the license and shift class design problem
• An analysis of shift class design problems
• Scheduling jobs within time windows on identical parallel machines: New model and algorithms
• Exact and approximation algorithms for the operational fixed interval scheduling problem
• On polynomial-time approximation algorithms for the variable length scheduling problem.
• Approximation algorithms for the workload partition problem and applications to scheduling with variable processing times
• On the approximability of an interval scheduling problem
• A lower bound for the job insertion problem.
• Job release scheduling problem: complexity and an approximation algorithm
• Inverse interval scheduling via reduction on a single machine
• Runway sequencing with holding patterns
• A metaheuristic for the fixed job scheduling problem under spread time constraints
• On holonomic mathematical F-pendulum
• Operational fixed job scheduling problem under spread time constraints: a branch-and-price algorithm
• Working time constraints in operational fixed job scheduling
• A fixed job scheduling problem with machine-dependent job weights
• Approximation Algorithms for the Assembly Line Crew Scheduling Problem
• Tactical fixed job scheduling with spread-time constraints
• Spread time considerations in operational fixed job scheduling
• The Fixed Job Schedule Problem with Spread-Time Constraints
• The Fixed Job Schedule Problem with Working-Time Constraints
• Algorithms for large scale shift minimisation personnel task scheduling problems
• scientific article; zbMATH DE number 1512677 (Why is no real title available?)
• APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS
• Cost constrained fixed job scheduling.
• The optimal cost chromatic partition problem for trees and interval graphs
• Approximation algorithms for time constrained scheduling
• Fixed interval scheduling: models, applications, computational complexity and algorithms

This page was built for publication: Approximation Algorithms for Fixed Job Schedule Problems

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