scientific article; zbMATH DE number 3550182
From MaRDI portal
zbMath0353.68067MaRDI QIDQ4124328
Alexander H. G. Rinnooy Kan, Peter Brucker, Jan Karel Lenstra
Publication date: 1977
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Deterministic scheduling theory in operations research (90B35) Algorithms in computer science (68W99)
Related Items
Some no-wait shops scheduling problems: Complexity aspect, A graph coloring approach to the deployment scheduling and unit assignment problem, Online production planning to maximize the number of on-time orders, Preemption in single machine earliness/tardiness scheduling, A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem, Optimal due date assignment in multi-machine scheduling environments, Effective on-line algorithms for reliable due date quotation and large-scale scheduling, Minimizing the stretch when scheduling flows of divisible requests, A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process, Exact algorithms for single-machine scheduling with time windows and precedence constraints, Total completion time minimization on multiple machines subject to machine availability and makespan constraints, Solving the traveling repairman problem on a line with general processing times and deadlines, Design of automated negotiation mechanisms for decentralized heterogeneous machine scheduling, On a scheduling problem where a job can be executed only by a limited number of processors, An assignment-based lower bound for a class of two-machine flow shop problems, Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties, A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times, A best possible on-line algorithm for two-machine flow shop scheduling to minimize makespan, An effective lower bound on \(L_{\max}\) in a worker-constrained job shop, Two-agent singe-machine scheduling with release times to minimize the total weighted completion time, Finding optimal tour schedules on transportation paths under extended time window constraints, Bicriteria scheduling problem for unrelated parallel machines with release dates, Acquisition planning and scheduling of computing resources, A study on several combination problems of classic shop scheduling and shortest path, The two-machine flowshop scheduling problem with total tardiness, Scheduling algorithms based on necessary optimality conditions, Single machine total tardiness maximization problems: complexity and algorithms, Tradeoff solutions in single machine production scheduling for minimizing flow time and maximum penalty, A branch-and-bound algorithm to solve the equal-execution-time job scheduling problem with precedence constraint and profile, New single machine and job-shop scheduling problems with availability constraints, Pre-emptive scheduling problems with controllable processing times, A survey of single machine scheduling to minimize weighted number of tardy jobs, A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors, A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents, Developing feasible and optimal schedules of jobs on one machine, A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective, Single machine batch scheduling with release times and delivery costs, A note on reverse scheduling with maximum lateness objective, An artificial bee colony algorithm for the job shop scheduling problem with random processing times, Two-machine interval shop scheduling with time lags, A two-stage coupled algorithm for an integrated maintenance planning and flowshop scheduling problem with deteriorating machines, Optimal control of a two-server flow-shop network, A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem, Resource constraint scheduling with a fractional shared resource, A hybrid differential evolution and tree search algorithm for the job shop scheduling problem, Scheduling and fixed-parameter tractability, Optimal results and numerical simulations for flow shop scheduling problems, A PMBGA to optimize the selection of rules for job shop scheduling based on the Giffler-Thompson algorithm, Matching based very large-scale neighborhoods for parallel machine scheduling, Preemptive scheduling of equal-length jobs in polynomial time, Solving job shop scheduling with setup times through constraint-based iterative sampling: an experimental analysis, Mathematical model applied to single-track line scheduling problem in Brazilian railways, Dominance rules for the parallel machine total weighted tardiness scheduling problem with release dates, Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs, New dominance rules and exploration strategies for the \(1|r _{i}|\sum U _{i }\) scheduling problem, General approximation algorithms for some arithmetical combinatorial problems, On the continuous working problem, A controlled search simulated annealing method for the single machine weighted tardiness problem, Constraint programming approach to a bilevel scheduling problem, Bottleneck machine identification method based on constraint transformation for job shop scheduling with genetic algorithm, Notes on inverse bin-packing problems, Approximation results in parallel machines stochastic scheduling, Reducibility among single machine weighted completion time scheduling problems, An algorithm for single machine sequencing with release dates to minimize total weighted completion time, Surrogate duality relaxation for job shop scheduling, Two-agent single-machine scheduling of jobs with time-dependent processing times and ready times, Inventory based bi-objective flow shop scheduling model and its hybrid genetic algorithm, A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration, Approximation algorithms for no idle time scheduling on a single machine with release times and delivery times, Deadline constrained cyclic scheduling on pipelined dedicated processors considering multiprocessor tasks and changeover times, Minimizing value-at-risk in single-machine scheduling, A time indexed formulation of non-preemptive single machine scheduling problems, A two-machine flowshop problem with processing time-dependent buffer constraints-an application in multimedia presentations, Scheduling partially ordered jobs faster than \(2^n\), Single machine scheduling with nonlinear lateness cost functions and fuzzy due dates, Sequencing a single machine with due dates and deadlines: An ILP-based approach to solve very large instances, A tabu-search algorithm for scheduling jobs with controllable processing times on a single machine to meet due-dates, Crane scheduling in container yards with inter-crane interference, A two-machine flowshop problem with two agents, Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment, A decomposition scheme for single stage scheduling problems, Performance of the LPT algorithm in multiprocessor scheduling, Complexity of single machine scheduling subject to nonnegative inventory constraints, Analysis of the similarities and differences of job-based scheduling problems, Exact and heuristic algorithms for minimizing tardy/lost penalties on a single-machine scheduling problem, Solving scheduling and location problems in the plane simultaneously, Optimal solutions for a dock assignment problem with trailer transportation, Discrete-continuous project scheduling with discounted cash inflows and various payment models -- a review of recent results, The one-machine just-in-time scheduling problem with preemption, An empirical analysis of the optimality rate of flow shop heuristics, Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness, The Pareto frontier of inefficiency in mechanism design, Lagrangian domain reductions for the single machine earliness-tardiness problem with release dates, Effective optimization methods for single-machine scheduling (survey), New directions in scheduling theory, Algorithms for two-machine flow-shop sequencing with precedence constraints, Linear programming models for load balancing, Speed scaling for maximum lateness, Integrated production and distribution scheduling problems related with fixed delivery departure dates and number of late orders, The coordination of scheduling and batch deliveries, Integrated production and outbound distribution scheduling problems with job release dates and deadlines, A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, Optimizing termination decision for meta-heuristic search techniques that converge to a static objective-value distribution, Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup times, Approximation schemes for parallel machine scheduling problems with controllable processing times, A look-ahead heuristic for scheduling jobs with release dates on a single machine, NP-hardness of shop-scheduling problems with three jobs, Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches, An efficient algorithm for a job shop problem, Minimizing the sum of weighted completion times with unrestricted weights, A comprehensive review of flowshop group scheduling literature, Metaheuristics for the single machine weighted quadratic tardiness scheduling problem, Efficient local search limitation strategy for single machine total weighted tardiness scheduling with sequence-dependent setup times, Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times, Algorithms for the unrelated parallel machine scheduling problem with a resource constraint, Asymptotic optimality of statistical multiplexing in pipelined processing, On the fine-grained parameterized complexity of partial scheduling to minimize the makespan, Scheduling parallel machines to minimize total weighted and unweighted tardiness, A decomposition-based two-stage optimization algorithm for single machine scheduling problems with deteriorating jobs, On the complexity of two machine job-shop scheduling with regular objective functions, A branch and bound algorithm to minimize the total weighed number of tardy jobs and delivery costs, On a scheduling problem in a robotized analytical system, A sequencing problem with family setup times, Coordinated optimization of production scheduling and maintenance activities with machine reliability deterioration, Estimation of the absolute error and polynomial solvability for a classical NP-hard scheduling problem, The quality of equilibria for set packing and throughput scheduling games, A truncated column generation algorithm for the parallel batch scheduling problem to minimize total flow time, An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown, A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem, Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices, Scheduling personnel for the build-up of unit load devices at an air cargo terminal with limited space, Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network, On the exact solution of a large class of parallel machine scheduling problems, GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times, Spatial-domain fitness landscape analysis for combinatorial optimization, Scheduling jobs with sizes and delivery times on identical parallel batch machines, Scheduling in a multi-processor environment with deteriorating job processing times and decreasing values: the case of forest fires, Approximation algorithms for some position-dependent scheduling problems, A local search algorithm for the flow shop scheduling problem with release dates, Improved bounded dynamic programming algorithm for solving the blocking flow shop problem, Metaheuristics for order scheduling problem with unequal ready times, Scheduling with limited machine availability, Scheduling with variable-length calibrations: two agreeable variants, Two-machine flowshop scheduling in a physical examination center, An iterated local search procedure for the job sequencing and tool switching problem with non-identical parallel machines, A metric approach for scheduling problems with minimizing the maximum penalty, Task scheduling with interprocessor communication delays, A simulation-based study of dispatching rules in a dynamic job shop scheduling problem with batch release and extended technical precedence constraints, Matching supply and demand in a sharing economy: classification, computational complexity, and application, A review of open queueing network models of manufacturing systems, A new hybrid genetic algorithm for job shop scheduling problem, An empirical analysis of heuristics for solving the two-machine flow shop problem with job release times, An exact approach for scheduling jobs with regular step cost functions on a single machine, A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine, No-wait or no-idle permutation flowshop scheduling with dominating machines, Minimizing delays in a shunting yard, Upper and lower bounds for the permutation flowshop scheduling problem with minimal time lags, A computational study of the permutation flow shop problem based on a tight lower bound, Core instances for testing: a case study, Parameterized complexity of machine scheduling: 15 open problems, Single machine scheduling with nonlinear cost functions, Single-machine scheduling with an external resource, Bi-objective parallel machine scheduling with additional resources during setups, Minimizing maximum tardiness and delivery costs with batch delivery and job release times, Scheduling jobs with release and delivery times subject to nested eligibility constraints, A variable neighborhood descent as ILS local search to the minimization of the total weighted tardiness on unrelated parallel machines and sequence dependent setup times, Integrated scheduling of production and distribution with release dates and capacitated deliveries, Modeling single machine preemptive scheduling problems for computational efficiency, Scheduling equal length jobs with eligibility restrictions, A new approximation algorithm for unrelated parallel machine scheduling with release dates, Approximation schemes for minimizing the maximum lateness on a single machine with release times under non-availability or deadline constraints, Two machine flow shop scheduling problem with no wait in process: Controllable machine speeds, Lower bounds for the job-shop scheduling problem on multi-purpose machines, Some concepts of stability analysis in combinatorial optimization, Analysis of variable neighborhood descent as a local search operator for total weighted tardiness problem on unrelated parallel machines, A new branch and bound algorithm for minimizing mean tardiness in two- machine flowshops, Parallel machine makespan minimization subject to machine availability and total completion time constraints, The job shop scheduling problem: Conventional and new solution techniques, Makespan minimization with OR-precedence constraints, Disruption recovery at airports: ground holding, curfew restrictions and an approximation algorithm, Scheduling periodic I/O access with bi-colored chains: models and algorithms, Scheduling unit processing time jobs on a single machine with multiple criteria, Metric interpolation for the problem of minimizing the maximum lateness for a single machine, Parallel execution of schedules with random dependency graph, Approximability of flow shop scheduling, Minimizing average completion time in the presence of release dates, A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model, Randomized selection algorithm for online stochastic unrelated machines scheduling, Structural scheduling in the problems of scheduling theory, Order assignment and scheduling under processing and distribution time uncertainty, An adaptive TS approach to JIT sequencing with variable processing times and sequence-dependent setups, Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing, Decomposition methods for large job shops, Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion time, A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size, 2-approximation algorithm for minmax absolute maximum lateness scheduling-location problem, Scheduling two jobs with fixed and nonfixed routes, Using genetic algorithms for single-machine bicriteria scheduling problems, Combining constraint programming and temporal decomposition approaches -- scheduling of an industrial formulation plant, Performance guarantees of local search for minsum scheduling problems, Min-max relative regret for scheduling to minimize maximum lateness, Tabu search algorithms for minimizing total completion time on a single machine with an actual time-dependent learning effect, A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints, Minimizing the weighted number of tardy jobs on multiple machines: a review, Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs, Problem Decomposition and Multi-shot ASP Solving for Job-shop Scheduling, Approximation algorithms for minimizing the total weighted tardiness on a single machine, Scheduling Bidirectional Traffic on a Path, Task scheduling in networks, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Tower-of-sets analysis for the Kise-Ibaraki-Mine algorithm, Scheduling jobs that arrive over time, Outsourcing and scheduling for a two-machine flow shop with release times, Loading and scheduling for flexible manufacturing systems with controllable processing times, Parallel machine selection and job scheduling to minimize machine cost and job tardiness, Two very large-scale neighborhoods for single machine scheduling, Scheduling in supply chain environment, Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms, ON ONLINE SCHEDULING JOBS WITH RESTART TO MAXIMIZE THE NUMBER OF JOBS COMPLETED TIME ON A SINGLE MACHINE, The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays, Robust single machine makespan scheduling with release date uncertainty, Novel Formulations and Logic-Based Benders Decomposition for the Integrated Parallel Machine Scheduling and Location Problem, Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling, Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time, A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times, Multi-period bin packing model and effective constructive heuristics for corridor-based logistics capacity planning, Genetic programming-based hyper-heuristic approach for solving dynamic job shop scheduling problem with extended technical precedence constraints, Generalized order acceptance and scheduling problem with batch delivery: models and metaheuristics, When serial batch scheduling involves parallel batching decisions: a branch and price scheme, Instance space analysis and algorithm selection for the job shop scheduling problem, Robust scheduling with budgeted uncertainty, Exact algorithms for solving the constrained parallel-machine scheduling problems with divisible processing times and penalties, Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds, On some lower bounds for the permutation flowshop problem, Objective-based counterfactual explanations for linear discrete optimization, An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents, An 11/7 — Approximation Algorithm for Single Machine Scheduling Problem with Release and Delivery Times, Exact and metaheuristic algorithms for flow-shop scheduling problems with release dates, Point-to-point and milk run delivery scheduling: models, complexity results, and algorithms based on Benders decomposition, Joint replenishment meets scheduling, Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using inclusion-exclusion, Scheduling Algorithms for Single Machine Problem with Release and Delivery Times, Single machine scheduling with release dates: a distributionally robust approach, A state-of-the-art survey on multi-scenario scheduling, Dynamic scheduling of patients in emergency departments, A mixed integer formulation and an efficient metaheuristic for the unrelated parallel machine scheduling problem: total tardiness minimization, Competitive two-agent scheduling with release dates and preemption on a single machine, An Exact Algorithm for the Single-Machine Earliness–Tardiness Scheduling Problem, Polynomially solvable subcases for the approximate solution of multi-machine scheduling problems, Hybrid evolutionary algorithm with optimized operators for total weighted tardiness problem, Towards a Robust Scheduling on Unrelated Parallel Machines: A Scenarios Based Approach, Bicriteria multi-machine scheduling with equal processing times subject to release dates, Proportionate Flow Shop Scheduling with Rejection, Pareto optimal algorithms for minimizing total (weighted) completion time and maximum cost on a single machine, A historical note on the complexity of scheduling problems, The constrained parallel-machine scheduling problem with divisible processing times and penalties, Application of the interpolation approach for approximating single-machine scheduling problem with an unknown objective function, On the complexity of scheduling problems with a fixed number of parallel identical machines, A best possible online algorithm for minimizing the total completion time and the total soft penalty cost, Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods, Parallel machine problems with equal processing times: a survey, Single-machine scheduling with no idle time and release dates to~minimize a regular criterion, Optimality proof of the Kise-Ibaraki-Mine algorithm, A complete 4-parametric complexity classification of short shop scheduling problems, A linear programming-based method for job shop scheduling, Scheduling of inventory releasing jobs to satisfy time-varying demand: an analysis of complexity, Scheduling Massively Parallel Multigrid for Multilevel Monte Carlo Methods, Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time, The Vehicle Routing Problem with Release and Due Dates, A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching, Integrated Scheduling of Production and Two-Stage Delivery of Make-to-Order Products: Offline and Online Algorithms, Reoptimization in machine scheduling, Unnamed Item, Approximation algorithms for scheduling problems with a modified total weighted tardiness objective, Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds, Analysis of a linearization heuristic for single-machine scheduling to maximize profit, On the Integration of Theoretical Single-Objective Scheduling Results for Multi-objective Problems, A prediction based iterative decomposition algorithm for scheduling large-scale job shops, Shiftable intervals, Grasp and delivery for moving objects on broken lines, Scheduling of a single machine to minimize total weighted completion time subject to release dates, Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem, Lexicographic optimization of a permutation flow shop scheduling problem with time lag constraints, Single Machine Preemptive Scheduling to Minimize the Weighted Number of Late Jobs with Deadlines and Nested Release/Due Date Intervals, Yard crane scheduling in port container terminals, A computational study with a new algorithm for the three-machine permutation flow-shop problem with release times, The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates, Server cloud scheduling, A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time, An efficient ILP formulation for the single machine scheduling problem, A 3/2-approximation algorithm for two-machine flow-shop sequencing subject to release dates., Bounding the Running Time of Algorithms for Scheduling and Packing Problems, Using Lagrangean relaxation to minimize the weighted number of late jobs on a single machine, A resource constrained scheduling problem with multiple independent producers and a single linking constraint: a coal supply chain example, Lower and Upper Bounds for the Preemptive Single Machine Scheduling Problem with Equal Processing Times, A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems, Scheduling a single machine with primary and secondary objectives, Stochastic Online Scheduling Revisited, Approximation algorithms and an FPTAS for the single machine problem with biased tardiness penalty, Consistency techniques for polytime linear global cost functions in weighted constraint satisfaction, Decision Incorporation in Meta-heuristics to Cope with Decision Scheduling Problems, Constant Factor Approximation Algorithm for Weighted Flow-Time on a Single Machine in PseudoPolynomial Time
