The one-machine sequencing problem

DOI10.1016/S0377-2217(82)80007-6zbMath0482.90045MaRDI QIDQ1162927

Publication date: 1982

Published in: European Journal of Operational Research (Search for Journal in Brave)

computational complexity; NP-hardness; minimization of makespan; efficient branch and bound methods; one-machine sequencing; Schrage schedule; tree-search

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90B35: Deterministic scheduling theory in operations research

Related Items

Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times, Scheduling batch processing machines with incompatible job families, Measures of subproblem criticality in decomposition algorithms for shop scheduling, Scheduling Equal-Length Jobs with Delivery times on Identical Processors, A modified shifting bottleneck procedure for job-shop scheduling, An efficient ILP formulation for the single machine scheduling problem, Scheduling with tails and deadlines, Local search algorithms for a single-machine scheduling problem with positive and negative time-lags, Improving the preemptive bound for the single machine dynamic maximum lateness problem, Jackson's pseudo-preemptive schedule and cumulative scheduling problems, Local adjustments: A general algorithm, Event-based MILP models for resource-constrained project scheduling problems, New directions in scheduling theory, A robust approach for the single machine scheduling problem, Job shop scheduling with setup times, deadlines and precedence constraints, Permutation-induced acyclic networks for the job shop scheduling problem, Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval, Approximation algorithms for scheduling real-time jobs with multiple feasible intervals, A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags, On the representation of the one machine sequencing problem in the shifting bottleneck heuristic, New single machine and job-shop scheduling problems with availability constraints, Hybrid decomposition heuristics for solving large-scale scheduling problems in semiconductor wafer fabrication, A branch and bound method for the job-shop problem with sequence-dependent setup times, On single-machine scheduling without intermediate delays, Jackson's semi-preemptive scheduling on a single machine, Scheduling trains as a blocking parallel-machine job shop scheduling problem, \texttt{Absalom}: balancing assembly lines with assignment restrictions, A note on minimizing maximum lateness in a one-machine sequencing problem with release dates, A block approach for single-machine scheduling with release dates and due dates, Scheduling jobs with release dates and tails on identical machines to minimize the makespan, An algorithm for single machine sequencing with release dates to minimize maximum cost, A procedure for the one-machine sequencing problem with dependent jobs, Scheduling jobs on a single machine with release dates, delivery times and controllable processing times: Worst-case analysis, Scheduling with release dates on a single machine to minimize total weighted completion time, A time indexed formulation of non-preemptive single machine scheduling problems, One-machine rescheduling heuristics with efficiency and stability as criteria, Two branch and bound algorithms for the permutation flow shop problem, Extending the shifting bottleneck procedure to real-life applications, The job shop scheduling problem: Conventional and new solution techniques, The generalized shifting bottleneck procedure, A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem, Time lag size in multiple operations flow shop scheduling heuristics, A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags, Reduction of job-shop problems to flow-shop problems with precedence constraints, An O\((n^4)\) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs, An approximation algorithm for a single-machine scheduling problem with release times and delivery times, An approximation algorithm for a single-machine scheduling problem with release times, delivery times and controllable processing times, A branch and bound algorithm for the job-shop scheduling problem, Preemptive scheduling with release dates, delivery times and sequence independent setup times, A decomposition approach for a resource constrained scheduling problem, The job-shop problem and immediate selection, Adjustment of heads and tails for the job-shop problem, Evolution based learning in a job shop scheduling environment, Fast algorithms to minimize the makespan or maximum lateness in the two-machine flow shop with release times., A branch \(\&\) bound algorithm for the open-shop problem, Branch and bound methods for scheduling problems with multiprocessor tasks on dedicated processors, Job-shop scheduling: Computational study of local search and large-step optimization methods, Minimizing flow time in cyclic schedules for identical jobs with acyclic precedence: The bottleneck lower bound., Decomposition methods for reentrant flow shops with sequence-dependent setup times, Efficiency of reductions of job-shop to flow-shop problems, Constraint propagation techniques for the disjunctive scheduling problem, Concurrent operations can be parallelized in scheduling multiprocessor job shop, Minimizing makespan on parallel machines subject to release dates and delivery times, A computational study of the permutation flow shop problem based on a tight lower bound, Core instances for testing: a case study, Resource-constrained project scheduling: Notation, classification, models, and methods, Deterministic job-shop scheduling: Past, present and future, Using short-term memory to minimize the weighted number of late jobs on a single machine., Job-shop scheduling with blocking and no-wait constraints, A branch and bound to minimize the number of late jobs on a single machine with release time constraints, An improved shifting bottleneck procedure for the job shop scheduling problem, A sequencing problem with family setup times, Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan, A tabu search method guided by shifting bottleneck for the job shop scheduling problem, Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints, A branch and bound algorithm for scheduling trains in a railway network, A branch and bound algorithm for scheduling jobs with controllable processing times on a single machine to meet due dates, An approximate decomposition algorithm for scheduling on parallel machines with heads and tails, Application of an optimization problem in max-plus algebra to scheduling problems, Heuristics for minimizing maximum lateness on a single machine with family-dependent set-up times, A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates, Single machine scheduling subject to precedence delays, Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem, Applying machine based decomposition in 2-machine flow shops, Study on constraint scheduling algorithm for job shop problems with multiple constraint machines, Unnamed Item

Cites Work