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

DOI10.1007/s10951-021-00677-8OpenAlexW3139253831MaRDI QIDQ6204660

Zhen-bo Wang, Kameng Nip

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 schedulingopen shop schedulingflow 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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scheduling under linear constraints
• Minimax linear programming problem
• Approximability of flow shop scheduling
• Makespan minimization in open shops: A polynomial time approximation scheme
• Using two-machine flowshop with maximum lateness objective to model multimedia data objects scheduling problem for WWW applications
• Bin packing under linear constraints
• Knapsack with variable weights satisfying linear constraints
• Two-machine flow shop scheduling problem under linear constraints
• Optimal two- and three-stage production schedules with setup times included
• Open Shop Scheduling to Minimize Finish Time
• The Complexity of Flowshop and Jobshop Scheduling
• Computational Complexity of Discrete Optimization Problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Improved Approximation Algorithms for Shop Scheduling Problems
• Short Shop Schedules
• Makespan Minimization in Job Shops: A Linear Time Approximation Scheme
• Application of Programs with Maximin Objective Functions to Problems of Optimal Resource Allocation
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• A Branch-and-Bound Approach for a Two-machine Flowshop Scheduling Problem
• Hardness of Approximating Flow and Job Shop Scheduling Problems
• Scheduling
• Some graph optimization problems with weights satisfying linear constraints
• Related machine scheduling with machine speeds satisfying linear constraints

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