The one-machine sequencing problem

DOI10.1016/S0377-2217(82)80007-6MaRDI QIDQ1162927zbMATH OpenFDO

Authors Jacques Carlier

Publication date 1982

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

zbMATH Keywords

computational complexityNP-hardnessminimization of makespanefficient branch and bound methodsone-machine sequencingSchrage scheduletree-search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Cites work

• scientific article; zbMATH DE number 3604658 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3378735 (Why is no real title available?)
• Minimizing maximum lateness on one machine: computational experience and some applications
• On sequencing with earliest starts and due dates with application to computing bounds for the (n/m/G/F_max) problem
• Sequencing with due-dates and early start times to minimize maximum tardiness

Cited in

(only showing first 100 items - show all)

• Depth-first heuristic search for the job shop scheduling problem
• A robust approach for the single machine scheduling problem
• Deterministic job-shop scheduling: Past, present and future
• Hybrid decomposition heuristics for solving large-scale scheduling problems in semiconductor wafer fabrication
• A branch and bound algorithm for scheduling trains in a railway network
• Two branch and bound algorithms for the permutation flow shop problem
• A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags
• Preemptive scheduling with release dates, delivery times and sequence independent setup times
• A job-shop problem with one additional resource type
• Using short-term memory to minimize the weighted number of late jobs on a single machine.
• Decomposition methods for reentrant flow shops with sequence-dependent setup times
• Minimizing makespan on parallel machines subject to release dates and delivery times
• Scheduling jobs on a single machine with release dates, delivery times and controllable processing times: Worst-case analysis
• An exact method for the bi-objective one-machine problem with maximum lateness and unit family setup cost objectives
• Evolution based learning in a job shop scheduling environment
• An improved branch-and-bound algorithm for the one-machine scheduling problem with delayed precedence constraints
• Developing feasible and optimal schedules of jobs on one machine
• Two-stage hybrid flow shop with precedence constraints and parallel machines at second stage
• Competitive two-agent scheduling with release dates and preemption on a single machine
• An approximation algorithm for a single-machine scheduling problem with release times and delivery times
• Application of an optimization problem in max-plus algebra to scheduling problems
• A branch \(\&\) bound algorithm for the open-shop problem
• Scheduling jobs on parallel machines to minimize a regular step total cost function
• Branch and bound methods for scheduling problems with multiprocessor tasks on dedicated processors
• An \(O(n^2)\) algorithm for time-bound adjustments for the cumulative scheduling problem
• An exact approach for the 0-1 knapsack problem with setups
• Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem
• Job-shop scheduling with blocking and no-wait constraints
• Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints
• Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan
• Constraint propagation techniques for the disjunctive scheduling problem
• Polynomially solvable subcases for the approximate solution of multi-machine scheduling problems
• An exact block algorithm for no-idle RPQ problem
• 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
• An approximate decomposition algorithm for scheduling on parallel machines with heads and tails
• Minimizing maximum delivery completion time for order scheduling with rejection
• Scheduling with tails and deadlines
• An O\((n^4)\) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
• Concurrent operations can be parallelized in scheduling multiprocessor job shop
• Minimizing flow time in cyclic schedules for identical jobs with acyclic precedence: The bottleneck lower bound.
• Complexity, bounds and dynamic programming algorithms for single track train scheduling
• Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times
• Improving branch and bound for jobshop scheduling with constraint propagation
• Permutation-induced acyclic networks for the job shop scheduling problem
• Scheduling a single machine with primary and secondary objectives
• An efficient ILP formulation for the single machine scheduling problem
• Constraint programming and operations research
• A branch and bound algorithm for scheduling jobs with controllable processing times on a single machine to meet due dates
• Scheduling batch processing machines with incompatible job families
• The generalized shifting bottleneck procedure
• Local adjustments: A general algorithm
• Approximation algorithms for scheduling real-time jobs with multiple feasible intervals
• \texttt{Absalom}: balancing assembly lines with assignment restrictions
• A branch and bound to minimize the number of late jobs on a single machine with release time constraints
• Scheduling in manufacturing with transportation: classification and solution techniques
• Scheduling Algorithms for Single Machine Problem with Release and Delivery Times
• Fast algorithms to minimize the makespan or maximum lateness in the two-machine flow shop with release times.
• Scheduling jobs with release dates and tails on identical machines to minimize the makespan
• The job-shop problem and immediate selection
• A sequencing problem with family setup times
• An algorithm for single machine sequencing with release dates to minimize maximum cost
• A modified shifting bottleneck procedure for job-shop scheduling
• Jackson's semi-preemptive scheduling on a single machine
• A novel MILP model for \(N\)-vehicle exploration problem
• Event-based MILP models for resource-constrained project scheduling problems
• A branch-and-bound method for the single-machine scheduling problem under a non-availability constraint for maximum delivery time minimization
• Scheduling Equal-Length Jobs with Delivery times on Identical Processors
• Logic-based Benders decomposition for the preemptive flexible job-shop scheduling problem
• Extending the single machine-based relaxation scheme for the job shop scheduling problem
• Scheduling with release dates on a single machine to minimize total weighted completion time
• A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem
• A time indexed formulation of non-preemptive single machine scheduling problems
• Integrated production and outbound distribution scheduling problems with job release dates and deadlines
• scientific article; zbMATH DE number 1271322 (Why is no real title available?)
• A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags
• Adjustment of heads and tails for the job-shop problem
• Time lag size in multiple operations flow shop scheduling heuristics
• \textit{Branch} \& \textit{memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees
• A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates
• Reduction of job-shop problems to flow-shop problems with precedence constraints
• A metric approach for scheduling problems with minimizing the maximum penalty
• A decomposition approach for a resource constrained scheduling problem
• SALSA: combining branch-and-bound with dynamic programming to smoothen workloads in simple assembly line balancing
• Evaluation of a new decision-aid parameter for job shop scheduling under uncertainties
• On the representation of the one machine sequencing problem in the shifting bottleneck heuristic
• Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval
• Applying machine based decomposition in 2-machine flow shops
• New single machine and job-shop scheduling problems with availability constraints
• Efficiency of reductions of job-shop to flow-shop problems
• Improving the preemptive bound for the single machine dynamic maximum lateness problem
• Measures of subproblem criticality in decomposition algorithms for shop scheduling
• Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval
• A tabu search method guided by shifting bottleneck for the job shop scheduling problem
• Core instances for testing: a case study
• A cutting plane approach for integrated planning and scheduling
• One-machine rescheduling heuristics with efficiency and stability as criteria
• Resource-constrained project scheduling: Notation, classification, models, and methods
• An exact approach for single machine subproblems in shifting bottleneck procedures for job shops with total weighted tardiness objective
• A branch and bound algorithm for the job-shop scheduling problem

This page was built for publication: The one-machine sequencing problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1162927)