Open Shop Scheduling to Minimize Finish Time

DOI10.1145/321978.321985zbMath0343.68031OpenAlexW2093229192WikidataQ56442577 ScholiaQ56442577MaRDI QIDQ4111095

Teofilo F. Gonzalez, Sartaj K. Sahni

Publication date: 1976

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321978.321985

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algorithms in computer science (68W99)

Related Items

Lot streaming in three-stage production processes, Two machine open shop scheduling problems with bi-criteria, Two-machine open-shop scheduling with rejection to minimize the makespan, On the complexity of preemptive openshop scheduling problems, A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job, On some geometric methods in scheduling theory: A survey, Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications, Minimizing the stretch when scheduling flows of divisible requests, The two-machine no-wait general and proportionate open shop makespan problem, On the \(m\)-clique free interval subgraphs polytope: polyhedral analysis and applications, Complexity analysis of job-shop scheduling with deteriorating jobs, An extended study on an open-shop scheduling problem using the minimisation of the sum of quadratic completion times, A branch \(\&\) bound algorithm for the open-shop problem, Open shop problem with zero-one time operations and integer release date/deadline intervals, Flexible open shop scheduling problem to minimize makespan, A study on several combination problems of classic shop scheduling and shortest path, Minimizing expected makespan in a two-machine stochastic open shop with Poisson arrival, An open shop scheduling problem with a non-bottleneck machine, Two-stage no-wait scheduling models with setup and removal times separated, Open shop scheduling with maximal machines, Polynomial-time approximation schemes for scheduling problems with time lags, A tabu search algorithm for the open shop problem, A new three-machine shop scheduling: complexity and approximation algorithm, Approximation algorithms for two-machine open shop scheduling with batch and delivery coordination, Scheduling on power-heterogeneous processors, Cost-minimal preemptive scheduling of independent jobs with release and due dates on open shop under resource constraints, A survey on offline scheduling with rejection, Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, Jenő Egerváry: from the origins of the Hungarian algorithm to satellite communication, Properties of optimal schedules in preemptive shop scheduling, Routing open shop and flow shop scheduling problems, On the complexity of constructing multiprocessor little-preemptive schedules, Partially concurrent open shop scheduling with integral preemptions, Scheduling periodically occurring tasks on multiple processors, New bounds for optimum traffic assignment in satellite communication., Open shop scheduling with synchronization, Scheduling problems for parallel dedicated machines under multiple resource constraints., Open shop scheduling problems with late work criteria., An efficient tabu search approach for the two-machine preemptive open shop scheduling problem., Scheduling open shops with parallel machines, Almost nonpreemptive schedules, On the complexity of generalized due date scheduling problems, The complexity of shop-scheduling problems with two or three jobs, OSGA: genetic-based open-shop scheduling with consideration of machine maintenance in small and medium enterprises, On the geometry, preemptions and complexity of multiprocessor and shop scheduling, On the optimality of static policy in stochastic open shop, Approximability of average completion time scheduling on unrelated machines, Open shop cyclic scheduling, Dense open-shop schedules with release times, Two scheduling problems with fuzzy due-dates, Open shop scheduling with machine dependent processing times, New algorithms and complexity status of the reducibility problem of sequences in open shop scheduling minimizing the makespan, An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times, The museum visitor routing problem, A projective algorithm for preemptive open shop scheduling with two multiprocessor groups, An improved approximation algorithm for the partial Latin square extension problem., Chromatic scheduling in a cyclic open shop, On the open-shop problem with preemption and minimizing the average completion time, Scheduling two-machine no-wait open shops to minimize makespan, Scheduling preemptive open shops to minimize total tardiness, An introduction to multi-parameter complexity analysis of discrete problems, A \(\frac 6 5\)-approximation algorithm for the two-machine routing open-shop problem on a two-node network, Parameterized complexity of machine scheduling: 15 open problems, Scheduling ordered open shops, Two-machine flow shop and open shop scheduling problems with a single maintenance window, Two-machine shop scheduling problems with batch processing, A genetic algorithm for the proportionate multiprocessor open shop, Polynomial time approximation algorithms for machine scheduling: Ten open problems, Isomorphic scheduling problems, The generalized shifting bottleneck procedure, Extensions of coloring models for scheduling purposes, A note on the proof of the complexity of the little-preemptive open-shop problem, Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors, Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop, A hybrid genetic algorithm for the open shop scheduling problem, Approximability of flow shop scheduling, Makespan minimization in open shops: A polynomial time approximation scheme, Minimizing average completion time in the presence of release dates, Approximation algorithms for two-machine flow shop scheduling with batch setup times, Group technology approach to the open shop scheduling problem with batch setup times, Scheduling incompatible tasks on two machines, Classical and new heuristics for the open-shop problem: A computational evaluation, A heuristic for the two-machine open-shop scheduling problem with transportation times, Using intelligent backtracking to improve branch-and-bound methods: An application to Open-Shop problems, Flow shop and open shop scheduling with a critical machine and two operations per job, Approximation algorithms for the multiprocessor open shop scheduling problem, Lot streaming in open shops, Two-stage open shop scheduling with a bottleneck machine, On the complexity of preemptive open-shop scheduling problems, Worst-case analysis of heuristics for open shops with parallel machines, Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function, Constructive heuristic algorithms for the open shop problem, Scheduling two jobs with fixed and nonfixed routes, The total completion time open shop scheduling problem with a given sequence of jobs on one machine, A polynomial feasibility test for preemptive periodic scheduling of unrelated processors, The mixed shop scheduling problem, Scheduling unit time open shops to minimize the weighted number of late jobs, Local search with constraint propagation and conflict-based heuristics, A polynomial algorithm for the \([n/m/0,\;t_{ij}=1,\text{ tree}/C_{\max}\) open shop problem], An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems, Decomposing graphs into interval colorable subgraphs and no-wait multi-stage schedules, An FPTAS for scheduling with resource constraints, Optimization for cooperative task planning of heterogeneous multi-robot systems in an order picking warehouse, A new variable neighbourhood search with a constraint programming search strategy for the open shop scheduling problem with operation repetitions, A constraint programming-based iterated greedy algorithm for the open shop with sequence-dependent processing times and makespan minimization, A time-dependent switching mean-field game on networks motivated by optimal visiting problems, A state-of-the-art survey on multi-scenario scheduling, Approximation algorithms for two-machine proportionate routing open shop on a tree, On the complexity of scheduling unrelated parallel machines with limited preemptions, A genetic algorithm for scheduling open shops with conflict graphs to minimize the makespan, A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints, Scheduling batches with simultaneous job processing for two-machine shop problems, Completing Partial Schedules for Open Shop with Unit Processing Times and Routing, On-line scheduling of small open shops, Two-machine open shop scheduling with an availability constraint, Bounding the Running Time of Algorithms for Scheduling and Packing Problems, Open-shop scheduling for unit jobs under precedence constraints, A PTAS for non-resumable open shop scheduling with an availability constraint, Two machine open shop scheduling problem with setup, processing and removal times separated, Scheduling two-machine preemptive open shops to minimize total completion time, Scheduling shops to minimize the weighted number of late jobs, A new particle swarm optimization for multi-objective open shop scheduling, NP-hardness of shop-scheduling problems with three jobs, An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times, Some positive news on the proportionate open shop problem, A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows, Scheduling jobs that arrive over time, Competitive two-agent scheduling problems to minimize the weighted combination of makespans in a two-machine open shop, Exponential tightness for integral-type functionals of centered independent differently distributed random variables, A survey of scheduling with controllable processing times, New efficient heuristics for scheduling open shops with makespan minimization, 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, Open shop scheduling problem with a non-resumable flexible maintenance period, A preemptive open shop scheduling problem with one resource, Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop, Asymptotic optimality of statistical multiplexing in pipelined processing, A novel complex network based dynamic rule selection approach for open shop scheduling problem with release dates, Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms, Open shop scheduling with some additional constraints, Unnamed Item, Nonpreemptive open shop with restricted processing times, Matching and scheduling of student-company-talks for a university it-speed dating event, Inhomogeneous deterministic two-stage queueing systems, Complexity of optimal scheduling problems with three jobs, Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass, Open shop, satellite communication and a theorem by Egerváry (1931), Two-machine open shop problem with a single server and set-up time considerations, On a routing Open Shop Problem on two nodes with unit processing times, Open shop scheduling with delays, A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times, A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops, Dual criteria preemptive open-shop problems with minimum makespan, Note: Open-shop scheduling with release dates to minimize maximum lateness, Unbounded parallel-batch scheduling with family jobs and delivery coordination, Open-shop dense schedules: properties and worst-case performance ratio, A complete 4-parametric complexity classification of short shop scheduling problems, Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments, Scheduling the two-machine open shop problem under resource constraints for setting the jobs, A tabu search approach for proportionate multiprocessor open shop scheduling, Complexity of mixed shop scheduling problems: A survey, Complexity of shop-scheduling problems with fixed number of jobs: a survey, Three is easy, two is hard: Open shop sum-batch scheduling problem refined, Two-machine open shop problem with controllable processing times, Open shop scheduling games, Four decades of research on the open-shop scheduling problem to minimize the makespan, Irreducible bin packing and normality in routing open shop, Scheduling for parallel dedicated machines with a single server, METAHEURISTICS FOR THE MIXED SHOP SCHEDULING PROBLEM, Minimizing makespan in a two-stage hybrid flow shop scheduling problem with open shop in one stage, A heuristic approach to minimize expected makespan in open shops subject to stochastic processing times and failures, On the asymptotic optimality and improved strategies of SPTB heuristic for open-shop scheduling problem, A new particle swarm optimization for the open shop scheduling problem, Two-machine open shop scheduling with secondary criteria, The routing open-shop problem on a network: complexity and approximation, A SIMULATED ANNEALING ALGORITHM FOR SYSTEM-ON-CHIP TEST SCHEDULING WITH, POWER AND PRECEDENCE CONSTRAINTS, Network flow approaches to pre-emptive open-shop scheduling problems with time-windows, Open block scheduling in optical communication networks, On a conjecture for the university timetabling problem, Dynamic programming approach for solving the open shop problem, Transporting jobs through a two‐machine open shop, Shop scheduling problems with pliable jobs, Optimal edge-coloring with edge rate constraints, An iterative improvement approach for the nonpreemptive open shop scheduling problem, An Optimal Constraint Programming Approach to the Open-Shop Problem, Minimizing the makespan in open‐shop scheduling problems with a convex resource consumption function, The two-machine open shop problem: To fit or not to fit, that is the question, NP-Complete operations research problems and approximation algorithms, A review of four decades of time-dependent scheduling: main results, new topics, and open problems, Multi-objective open shop scheduling by considering human error and preventive maintenance, A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing, A polynomial-time open-shop problem with an arbitrary number of machines, Integrality Property in Preemptive Parallel Machine Scheduling, Complete Complexity Classification of Short Shop Scheduling, Three-machine open shop with a bottleneck machine revisited, SOLVING THE OPEN SHOP SCHEDULING PROBLEM VIA A HYBRID GENETIC-VARIABLE NEIGHBORHOOD SEARCH ALGORITHM, Reversible-shop scheduling, Two machine mixed shop scheduling problem with controllable machine speeds, Minimizing the Makespan and Flowtime in Two-Machine Stochastic Open Shops, Performance analysis of rotation schedule and improved strategy for open shop problem to minimise makespan, SCHEDULING PROPORTIONALLY DETERIORATING JOBS IN TWO-MACHINE OPEN SHOP WITH A NON-BOTTLENECK MACHINE, Multicriteria scheduling, Two-machine shop scheduling: Compromise between flexibility and makespan value, Polynomial time approximation algorithms for proportionate open‐shop scheduling, O(log m)-approximation for the routing open shop problem, ON SOLVING MULTIMESSAGE MULTICASTING PROBLEMS, A genetic algorithm for scheduling open shops with sequence-dependent setup times, Polynomial-time approximation schemes for two-machine open shop scheduling with nonavailability constraints, Two-machine open shop problem with agreement graph, A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs, Green scheduling, flows and matchings, The complexity of two group scheduling problems, A linear time approximation scheme for makespan minimization in an open shop with release dates, Scheduling parallel dedicated machines under a single non-shared resource, A cyclical search for the two machine flow shop and open shop to minimise finishing time, Two-machine routing open shop: How long is the optimal makespan?, Open shop scheduling problems with conflict graphs