Open Shop Scheduling to Minimize Finish Time

DOI10.1145/321978.321985zbMath0343.68031WikidataQ56442577 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

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68W99: Algorithms in computer science

Related Items

Scheduling ordered open shops, An improved approximation algorithm for the partial Latin square extension problem., 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, Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications, Minimizing the stretch when scheduling flows of divisible requests, Almost nonpreemptive schedules, On the geometry, preemptions and complexity of multiprocessor and shop scheduling, Dense open-shop schedules with release times, A genetic algorithm for the proportionate multiprocessor open shop, Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop, Scheduling incompatible tasks on two machines, On the complexity of preemptive open-shop scheduling problems, A polynomial feasibility test for preemptive periodic scheduling of unrelated processors, The mixed shop scheduling problem, Minimizing expected makespan in a two-machine stochastic open shop with Poisson arrival, Cost-minimal preemptive scheduling of independent jobs with release and due dates on open shop under resource constraints, Scheduling periodically occurring tasks on multiple processors, Scheduling open shops with parallel machines, On the complexity of generalized due date scheduling problems, The complexity of shop-scheduling problems with two or three jobs, On the optimality of static policy in stochastic open shop, Two scheduling problems with fuzzy due-dates, Open shop scheduling with machine dependent processing times, The generalized shifting bottleneck procedure, Extensions of coloring models for scheduling purposes, Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors, 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, 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, Approximation algorithms for the multiprocessor open shop scheduling problem, Lot streaming in open shops, 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, Scheduling unit time open shops to minimize the weighted number of late jobs, A polynomial algorithm for the \([n/m/0,\;t_{ij}=1,\text{ tree}/C_{\max}\) open shop problem], Lot streaming in three-stage production processes, Two machine open shop scheduling problems with bi-criteria, On the complexity of preemptive openshop scheduling problems, On some geometric methods in scheduling theory: A survey, Complexity analysis of job-shop scheduling with deteriorating jobs, A branch \(\&\) bound algorithm for the open-shop problem, Open shop problem with zero-one time operations and integer release date/deadline intervals, 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, A tabu search algorithm for the open shop problem, Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, New bounds for optimum traffic assignment in satellite communication., 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., A hybrid genetic algorithm for the open shop scheduling problem, Group technology approach to the open shop scheduling problem with batch setup 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, Two-stage open shop scheduling with a bottleneck machine, The total completion time open shop scheduling problem with a given sequence of jobs on one machine, Local search with constraint propagation and conflict-based heuristics, An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems, Chromatic scheduling in a cyclic open shop, 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, Two-machine shop scheduling problems with batch processing, Polynomial time approximation algorithms for machine scheduling: Ten open problems, An iterative improvement approach for the nonpreemptive open shop scheduling problem, The two-machine open shop problem: To fit or not to fit, that is the question, A polynomial-time open-shop problem with an arbitrary number of machines, Reversible-shop scheduling, Two machine mixed shop scheduling problem with controllable machine speeds, 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, Scheduling two-machine preemptive open shops to minimize total completion time, Scheduling shops to minimize the weighted number of late jobs, NP-hardness of shop-scheduling problems with three jobs, Shop scheduling problems with multiprocessor tasks on dedicated processors, Asymptotic optimality of statistical multiplexing in pipelined processing, Open shop scheduling with some additional constraints, Open shop, satellite communication and a theorem by Egerváry (1931), Complexity of mixed shop scheduling problems: A survey, Two machine open shop scheduling problem with setup, processing and removal times separated, A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows, A survey of scheduling with controllable processing times, Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop, 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, A heuristic approach to minimize expected makespan in open shops subject to stochastic processing times and failures, A new particle swarm optimization for the open shop scheduling problem, The routing open-shop problem on a network: complexity and approximation, Network flow approaches to pre-emptive open-shop scheduling problems with time-windows, Open block scheduling in optical communication networks, Multicriteria scheduling, Nonpreemptive open shop with restricted processing times, Unnamed Item, Unnamed Item, Unnamed Item, METAHEURISTICS FOR THE MIXED SHOP SCHEDULING PROBLEM, A SIMULATED ANNEALING ALGORITHM FOR SYSTEM-ON-CHIP TEST SCHEDULING WITH, POWER AND PRECEDENCE CONSTRAINTS, Minimizing the makespan in open‐shop scheduling problems with a convex resource consumption function, Minimizing the Makespan and Flowtime in Two-Machine Stochastic Open Shops, Scheduling batches with simultaneous job processing for two-machine shop problems, On-line scheduling of small open shops, Two-machine open shop scheduling with an availability constraint, Two-machine shop scheduling: Compromise between flexibility and makespan value, A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs, A preemptive open shop scheduling problem with one resource, Unnamed Item, Two-machine open shop scheduling with secondary criteria, Integrality Property in Preemptive Parallel Machine Scheduling, Complete Complexity Classification of Short Shop Scheduling, SOLVING THE OPEN SHOP SCHEDULING PROBLEM VIA A HYBRID GENETIC-VARIABLE NEIGHBORHOOD SEARCH ALGORITHM, Polynomial-time approximation schemes for two-machine open shop scheduling with nonavailability constraints, Transporting jobs through a two‐machine open shop, Inhomogeneous deterministic two-stage queueing systems, Complexity of optimal scheduling problems with three jobs, Open shop scheduling with delays, NP-Complete operations research problems and approximation algorithms