The one-machine sequencing problem

From MaRDI portal

Publication:1162927

Jump to:navigation, search

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

Jacques Carlier

Publication date: 1982

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items

A branch and bound algorithm for the job-shop scheduling problem, Constraint programming and operations research, Integrated production and outbound distribution scheduling problems with job release dates and deadlines, Preemptive scheduling with release dates, delivery times and sequence independent setup times, An improved shifting bottleneck procedure for the job shop scheduling problem, A block approach for single-machine scheduling with release dates and due dates, A decomposition approach for a resource constrained scheduling problem, Minimizing maximum delivery completion time for order scheduling with rejection, The job-shop problem and immediate selection, A robust approach for the single machine scheduling problem, Job shop scheduling with setup times, deadlines and precedence constraints, A branch and bound algorithm for scheduling trains in a railway network, Adjustment of heads and tails for the job-shop problem, A branch-and-bound method for the single-machine scheduling problem under a non-availability constraint for maximum delivery time minimization, Evolution based learning in a job shop scheduling environment, Scheduling jobs with release dates and tails on identical machines to minimize the makespan, 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, Fast algorithms to minimize the makespan or maximum lateness in the two-machine flow shop with release times., Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval, Approximation algorithms for scheduling real-time jobs with multiple feasible intervals, An exact approach for the 0-1 knapsack problem with setups, A branch \(\&\) bound algorithm for the open-shop problem, Improving schedule stability in single-machine rescheduling for new operation insertion, Two simple and effective heuristics for minimizing the makespan in non-permutation flow shops, Branch and bound methods for scheduling problems with multiprocessor tasks on dedicated processors, Theoretical expectation versus practical performance of Jackson's heuristic, Depth-first heuristic search for the job shop scheduling problem, A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags, A sequencing problem with family setup times, An algorithm for single machine sequencing with release dates to minimize maximum cost, 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, Developing feasible and optimal schedules of jobs on one machine, A procedure for the one-machine sequencing problem with dependent jobs, Job-shop scheduling: Computational study of local search and large-step optimization methods, An \(O(n^2)\) algorithm for time-bound adjustments for the cumulative scheduling problem, Improving the preemptive bound for the single machine dynamic maximum lateness problem, Minimizing flow time in cyclic schedules for identical jobs with acyclic precedence: The bottleneck lower bound., Resource leveling in a machine environment, 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, Scheduling jobs on parallel machines to minimize a regular step total cost function, An exact approach for single machine subproblems in shifting bottleneck procedures for job shops with total weighted tardiness objective, A job-shop problem with one additional resource type, 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, Complexity, bounds and dynamic programming algorithms for single track train scheduling, A branch and bound method for the job-shop problem with sequence-dependent setup times, Heuristics for minimizing maximum lateness on a single machine with family-dependent set-up times, Scheduling jobs on a single machine with release dates, delivery times and controllable processing times: Worst-case analysis, A novel MILP model for \(N\)-vehicle exploration problem, SALSA: combining branch-and-bound with dynamic programming to smoothen workloads in simple assembly line balancing, Scheduling with release dates on a single machine to minimize total weighted completion time, A metric approach for scheduling problems with minimizing the maximum penalty, A time indexed formulation of non-preemptive single machine scheduling problems, On single-machine scheduling without intermediate delays, One-machine rescheduling heuristics with efficiency and stability as criteria, A mixed integer linear programming approach to minimize the number of late jobs with and without machine availability constraints, A cutting plane approach for integrated planning and scheduling, Two-stage hybrid flow shop with precedence constraints and parallel machines at second stage, Jackson's pseudo-preemptive schedule and cumulative scheduling problems, Local adjustments: A general algorithm, Event-based MILP models for resource-constrained project scheduling problems, Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints, A computational study of the permutation flow shop problem based on a tight lower bound, Core instances for testing: a case study, \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees, Jackson's semi-preemptive scheduling on a single machine, Minimizing maximum tardiness and delivery costs with batch delivery and job release times, Resource-constrained project scheduling: Notation, classification, models, and methods, Solving an integrated job-shop problem with human resource constraints, Deterministic job-shop scheduling: Past, present and future, Scheduling trains as a blocking parallel-machine job shop scheduling problem, Using short-term memory to minimize the weighted number of late jobs on a single machine., 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, \texttt{Absalom}: balancing assembly lines with assignment restrictions, Decomposition methods for reentrant flow shops with sequence-dependent setup times, A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags, Efficiency of reductions of job-shop to flow-shop problems, Reduction of job-shop problems to flow-shop problems with precedence constraints, Scheduling a single machine with primary and secondary objectives, New directions in scheduling theory, Constraint propagation techniques for the disjunctive scheduling problem, The nonpermutation flowshop scheduling problem: adjustment and bounding procedures, Job-shop scheduling with blocking and no-wait 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, A note on minimizing maximum lateness in a one-machine sequencing problem with release dates, An approximation algorithm for a single-machine scheduling problem with release times, delivery times and controllable processing times, Concurrent operations can be parallelized in scheduling multiprocessor job shop, Minimizing makespan on parallel machines subject to release dates and delivery times, A branch and bound to minimize the number of late jobs on a single machine with release time constraints, Scheduling Equal-Length Jobs with Delivery times on Identical Processors, An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints, A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times, Computational evaluation of cut-strengthening techniques in logic-based Benders' decomposition, An 11/7 — Approximation Algorithm for Single Machine Scheduling Problem with Release and Delivery Times, Scheduling Algorithms for Single Machine Problem with Release and Delivery Times, Competitive two-agent scheduling with release dates and preemption on a single machine, Polynomially solvable subcases for the approximate solution of multi-machine scheduling problems, Logic-based Benders decomposition for the preemptive flexible job-shop scheduling problem, Study on constraint scheduling algorithm for job shop problems with multiple constraint machines, Unnamed Item, A branch-and-check algorithm for minimizing the weighted number of late jobs on a single machine with release dates, Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times, Scheduling with tails and deadlines, Scheduling batch processing machines with incompatible job families, Unnamed Item, Unnamed Item, Local search algorithms for a single-machine scheduling problem with positive and negative time-lags, An efficient ILP formulation for the single machine scheduling problem, A modified shifting bottleneck procedure for job-shop scheduling, An exact block algorithm for no-idle RPQ problem, Measures of subproblem criticality in decomposition algorithms for shop scheduling, Evaluation of a new decision-aid parameter for job shop scheduling under uncertainties, 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

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1162927&oldid=13227847"