Polyhedral results for position-based scheduling of chains on a single machine

DOI10.1007/S10479-019-03180-8MaRDI QIDQ2288972zbMATH OpenOpenAlexFDO

Authors Markó Horváth, Tamás Kis

Publication date 20 January 2020

Published in Annals of Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10479-019-03180-8

zbMATH Keywords

cutting planespolyhedrascheduling

Mathematics Subject Classification ID

Linear programming (90C05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• Scheduling two chains of unit jobs on one machine: a polyhedral study
• Single-machine scheduling with precedence constraints and position-dependent processing times
• Single-Machine Scheduling Polyhedra with Precedence Constraints
• Scheduling chains with identical jobs and constant delays on a single machine
• A polyhedral approach to single-machine scheduling problems.

Cites work

• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• Algorithms for cost-aware scheduling
• Compact extended linear programming models
• Complexity of Scheduling under Precedence Constraints
• Complexity results for scheduling chains on a single machine
• Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
• Integer Programming
• Minimizing Total Tardiness on a Single Machine with Precedence Constraints
• NP-complete scheduling problems
• Non-approximability results for scheduling problems with minsum criteria
• On defining sets of vertices of the hypercube by linear inequalities
• On scheduling with non-increasing time slot cost to minimize total weighted completion time
• On the complexity of scheduling unit-time jobs with or-precedence constraints
• Optimal scheduling for two-processor systems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling jobs with position-dependent processing times
• Scheduling problems with position dependent job processing times: computational complexity results
• Scheduling with AND/OR Precedence Constraints
• Scheduling with variable time slot costs
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints

Cited in

(3)

• Scheduling chains with identical jobs and constant delays on a single machine
• Matchings under distance constraints. II.
• Scheduling two chains of unit jobs on one machine: a polyhedral study

This page was built for publication: Polyhedral results for position-based scheduling of chains on a single machine

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