Flowshop and Jobshop Schedules: Complexity and Approximation
From MaRDI portal
Publication:4147825
DOI10.1287/opre.26.1.36zbMath0371.90061OpenAlexW1967955864MaRDI QIDQ4147825
Sartaj K. Sahni, Teofilo F. Gonzalez
Publication date: 1978
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.26.1.36
Related Items
A note on worst-case analysis of approximation algorithms for a scheduling problem, Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph, The bipartite margin shop and maximum red matchings free of blue-red alternating cycles, Flow shop scheduling problems with deteriorating jobs on no-idle dominant machines, Two-machine ordered flowshop scheduling under random breakdowns, Job-shop scheduling with convex models of operations, Minimizing makespan in hybrid flowshops, Unnamed Item, Scheduling manufacturing systems for delayed product differentiation in agile manufacturing, Permutation flowshop scheduling with simple linear deterioration, Min–max regret criterion-based robust model for the permutation flow-shop scheduling problem, An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops, Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches, Shop scheduling problems with multiprocessor tasks on dedicated processors, An efficient algorithm for a job shop problem, A worst-case analysis of the three-machine flow shop scheduling, Polynomial time algorithms for the UET permutation flowshop problem with time delays, Minimizing maximum completion time in a proportionate flow shop with one machine of different speed, Several flow shop scheduling problems with truncated position-based learning effect, Flowshop scheduling with a general exponential learning effect, Minimizing total completion time in a two-stage hybrid flow shop with dedicated machines at the first stage, Permutation flowshop problems with bi-criterion makespan and total completion time objective and position-weighted learning effects, A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime, Two simple and effective heuristics for minimizing the makespan in non-permutation flow shops, Asymptotic optimality of statistical multiplexing in pipelined processing, APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS, A bicriteria flowshop scheduling problem with setup times, Inhomogeneous deterministic two-stage queueing systems, Makespan minimization in preemptive two machine job shops, Worst-case analysis of an approximation algorithm for flow-shop scheduling, A note on flow shop scheduling problems with a learning effect on no-idle dominant machines, Minimizing makespan for flow shop scheduling by combining simulated annealing with sequencing knowledge, A new three-machine shop scheduling: complexity and approximation algorithm, Local search methods for the flowshop scheduling problem with flowtime minimization, The optimal number of used machines in a two-stage flexible flowshop scheduling problem, A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops, Minimizing total completion time in two-stage hybrid flow shop with dedicated machines, Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, A new approximation algorithm for UET-scheduling with chain-type precedence constraints., Worst-case and numerical analysis of heuristic algorithms for flowshop scheduling problems with a time-dependent learning effect, The computational complexity analysis of the two-processor flowshop problems with position dependent job processing times, Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem, A local search algorithm for the flow shop scheduling problem with release dates, Surrogate duality relaxation for job shop scheduling, Some results of the worst-case analysis for flow shop scheduling with a learning effect, Flowshop scheduling problems with a position-dependent exponential learning effect, Complexity of mixed shop scheduling problems: A survey, On the complexity of generalized due date scheduling problems, A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan, On the geometry, preemptions and complexity of multiprocessor and shop scheduling, An FPTAS for the parallel two-stage flowshop problem, Some new results in flow shop scheduling, A bicriteria flowshop scheduling with a learning effect, Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds, Minimizing total completion time in a two-machine flowshop: Analysis of special cases, A state-of-the-art review on scheduling with learning effects, Online scheduling of ordered flow shops, Two machine flow shop scheduling problem with weighted WIP costs, A heuristic approach to minimize expected makespan in open shops subject to stochastic processing times and failures, New results in the worst-case analysis for flow-shop scheduling, Flow shop scheduling with heterogeneous workers, A two-machine flowshop scheduling problem with a truncated sum of processing-times-based learning function, Analysis of heuristics for the UET two-machine flow shop problem with time delays, Approximation schemes for job shop scheduling problems with controllable processing times, Flow shops with WIP and value added costs, Study on flow shop scheduling with sum-of-logarithm-processing-times-based learning effects, A branch-and-cut algorithm for scheduling of projects with variable-intensity activities, Designing PTASs for MIN-SUM scheduling problems, Two-machine flowshop scheduling problem with bounded processing times to minimize total completion time, Two-machine flowshop scheduling with job class setups to minimize total flowtime, Improved lower bounds for minimizing the sum of completion times of n jobs over m machines in a flow shop, Scheduling algorithms for flexible flowshops: Worst and average case performance, Approximation results for the two-machine job shop under limited machine availability, Polynomial time approximation algorithms for machine scheduling: Ten open problems, Stochastically minimizing total flowtime in flowshops with no waiting space, Deterministic job-shop scheduling: Past, present and future, NP-Complete operations research problems and approximation algorithms, The job shop scheduling problem: Conventional and new solution techniques, Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects, An exchange heuristic imbedded with simulated annealing for due-dates job-shop scheduling, A fast tabu search algorithm for the permutation flow-shop problem, A linear time approximation algorithm for permutation flow shop scheduling, Heuristics for the two-stage job shop scheduling problem with a bottleneck machine, On-line and semi-online scheduling for flow shop problems on two machines, A new constructive heuristic for the flowshop scheduling problem, Scheduling in network flow shops, A robust two-machine flow-shop scheduling model with scenario-dependent processing times, Some results of the worst-case analysis for flow shop scheduling, Reduction of job-shop problems to flow-shop problems with precedence constraints, Proportionate flow shop: New complexity results and models with due date assignment, A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times, Performance guarantees for flowshop heuristics to minimize makespan, Flow shop and open shop scheduling with a critical machine and two operations per job, Performance of scheduling algorithms for no-wait flowshops with parallel machines, Branch and bound algorithm for the flow shop with multiple processors, Approximation algorithms for shop scheduling problems with minsum objective, The complexity of cyclic shop scheduling problems, A combination of flow shop scheduling and the shortest path problem, A tabu search approach to machine scheduling, The two- and \(m\)-machine flowshop scheduling problems with bicriteria of makespan and mean flowtime, Distributed assembly permutation flow-shop scheduling problem with sequence-dependent set-up times using a novel biogeography-based optimization algorithm, Parameter less hybrid IG-Jaya approach for permutation flow shop scheduling problem, An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents, Research on m‐machine flow shop scheduling with truncated learning effects, Algorithms for a two‐machine flowshop problem with jobs of two classes, Efficient algorithms for flexible job shop scheduling with parallel machines, A general efficient neighborhood structure framework for the job-shop and flexible job-shop scheduling problems, A state-of-the-art survey on multi-scenario scheduling, A SIMPLE LOWER BOUND FOR TOTAL COMPLETION TIME MINIMIZATION IN A TWO-MACHINE FLOWSHOP, A note on scheduling flowshops with flexible stage ordering, Scheduling batches with simultaneous job processing for two-machine shop problems, Workface planning in synchronous production systems, Bounding the Running Time of Algorithms for Scheduling and Packing Problems
