A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints

DOI10.1007/S10951-021-00677-8MaRDI QIDQ6204660zbMATH OpenOpenAlexFDO

Authors Kameng Nip, Zhenbo Wang

Publication date 2 April 2024

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10951-021-00677-8

zbMATH Keywords

computational complexitylinear programmingjob shop schedulingflow shop schedulingopen shop scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Recommendations

• Two-machine flow shop scheduling problem under linear constraints
• Computational complexity and algorithms for two scheduling problems under linear constraints
• On the NP-hardness of two scheduling problems under linear constraints
• Scheduling under linear constraints
• New complexity results for shop scheduling problems with agreement graphs

Cites work

• scientific article; zbMATH DE number 3151220 (Why is no real title available?)
• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 1131479 (Why is no real title available?)
• scientific article; zbMATH DE number 2146482 (Why is no real title available?)
• scientific article; zbMATH DE number 3799380 (Why is no real title available?)
• A Branch-and-Bound Approach for a Two-machine Flowshop Scheduling Problem
• Application of Programs with Maximin Objective Functions to Problems of Optimal Resource Allocation
• Approximability of flow shop scheduling
• Bin packing under linear constraints
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Computational Complexity of Discrete Optimization Problems
• Hardness of approximating flow and job shop scheduling problems
• Improved Approximation Algorithms for Shop Scheduling Problems
• Knapsack with variable weights satisfying linear constraints
• Linear programming and its application.
• Makespan Minimization in Job Shops: A Linear Time Approximation Scheme
• Makespan minimization in open shops: A polynomial time approximation scheme
• Minimax linear programming problem
• Open Shop Scheduling to Minimize Finish Time
• Optimal two- and three-stage production schedules with set-up time included
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Related machine scheduling with machine speeds satisfying linear constraints
• Scheduling under linear constraints
• Scheduling. Theory, algorithms, and systems.
• Short Shop Schedules
• Some graph optimization problems with weights satisfying linear constraints
• The Complexity of Flowshop and Jobshop Scheduling
• Two-machine flow shop scheduling problem under linear constraints
• Using two-machine flowshop with maximum lateness objective to model multimedia data objects scheduling problem for WWW applications

Cited in

(2)

• Computational complexity and algorithms for two scheduling problems under linear constraints
• On the NP-hardness of two scheduling problems under linear constraints

This page was built for publication: A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints

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