A dual algorithm for the one-machine scheduling problem

DOI10.1007/BF01580393zbMath0359.90039MaRDI QIDQ4131996

Marshall L. Fisher

Publication date: 1977

Published in: Mathematical Programming (Search for Journal in Brave)

Mathematics Subject Classification ID

Integer programming (90C10) Deterministic scheduling theory in operations research (90B35)

Related Items

Rescheduling problems with allowing for the unexpected new jobs arrival, A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem, A bicriterion scheduling problem involving total flowtime and total tardiness, Dynamic programming and decomposition approaches for the single machine total tardiness problem, Improving the performance of enumerative search methods. I: Exploiting structure and intelligence, A new branch and bound algorithm for minimizing the weighted number of tardy jobs, An empirical study of policies to integrate reactive scheduling and control in just-in-time job shop environments, Minimizing the weighted number of tardy jobs on a single machine with release dates, A tabu method for a two-agent single-machine scheduling with deterioration jobs, Minimizing total tardiness in a two-machine re-entrant flowshop with sequence-dependent setup times, A branch and bound algorithm to minimize the total tardiness for \(m\)-machine permutation flowshop problems, An investigation on a two-agent single-machine scheduling problem with unequal release dates, Decomposition of the single machine total tardiness problem, The two-machine flowshop scheduling problem with total tardiness, A Branch-and-Bound approach to solve a Bicriterion Scheduling Problem involving Squared Flowtime and Maximum Tardiness, A heuristic approach to bicriteria scheduling, Chance-constrained model for uncertain job shop scheduling problem, Minimisation of total tardiness for identical parallel machine scheduling using genetic algorithm, A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents, Matheuristics: survey and synthesis, Integration of finished goods batch delivery into production scheduling via total tardiness minimization, A new lower bounding scheme for the total weighted tardiness problem., A Single Machine Bicriterion Scheduling Problem and an Optimizing Branch-and-Bound Procedure, A two-machine flowshop scheduling problem with precedence constraint on two jobs, Group scheduling with deteriorating jobs to minimize the total weighted number of late jobs, A controlled search simulated annealing method for the single machine weighted tardiness problem, An efficient tabu search approach for the two-machine preemptive open shop scheduling problem., Two-machine flowshop scheduling to minimize total tardiness, Surrogate duality relaxation for job shop scheduling, Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem, Two-agent single-machine scheduling of jobs with time-dependent processing times and ready times, Bicriteria scheduling with vacations on a single machine, Job lateness in a two-machine flowshop with setup times separated, Single machine sequencing with nonlinear multicriteria cost functions: An application of generalized dynamic programming, Minimizing total tardiness in a scheduling problem with a learning effect, Analysis of a linearization heuristic for single-machine scheduling to maximize profit, Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems, Some new efficient methods to solve the \(n/1/r_ i/\sum{}T_ i\) scheduling problem, Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness, A honey-bees optimization algorithm for a two-agent single-machine scheduling problem with ready times, Scheduling preemptive open shops to minimize total tardiness, A two-machine flowshop problem with two agents, A heuristic approach for single-machine scheduling with due dates and class setups., Single machine scheduling with nonlinear cost functions, Real-world extensions to scheduling algorithms based on Lagrangian relaxation, Minimizing tardiness in a two-machine flow-shop, The single-machine total tardiness problem with unequal release times and a linear deterioration, A hybrid approach to discrete mathematical programming, A survey of various tactics for generating Lagrangian multipliers in the context of Lagrangian duality, Deterministic job-shop scheduling: Past, present and future, A survey of algorithms for the single machine total weighted tardiness scheduling problem, Using short-term memory to minimize the weighted number of late jobs on a single machine., A neural network model for scheduling problems, A simulated annealing approach for the one-machine mean tardiness scheduling problem, An asymptotic two-phase algorithm to minimize total flow time for a two-machine flowshop, Single machine earliness and tardiness scheduling, Minimizing total flowtime and maximum job lateness in the twomachine flowshop system: a computerized algorithm, An empirical study of policies to integrate reactive scheduling and control in just-in-time job shop environments, A General Framework for Stochastic One-machine Scheduling Problems with Zero Release Times and No Partial Ordering, A decomposition algorithm for the single machine total tardiness problem, Minimizing the sum of squares lateness on a single machine, A heuristic for the single machine tardiness problem, Scheduling identical parallel machines to minimize total weighted completion time, A greedy heuristic for the mean tardiness sequencing problem, Mathematical programming formulations for machine scheduling: A survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Linear Programming Approach to the Cutting-Stock Problem
• A Dynamic Programming Approach to Sequencing Problems
• Coordinating Aggregate and Detailed Scheduling Decisions in the One-Machine Job Shop: Part I. Theory
• Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part I
• Constructive Duality in Integer Programming
• Minimizing Total Costs in One-Machine Scheduling
• Branch-and-Bound Strategies for Dynamic Programming
• The B<scp>oxstep</scp> Method for Large-Scale Optimization
• An experimental comparison of solution algorithms for the single-machine tardiness problem
• Validation of subgradient optimization
• Scheduling to Minimize Interaction Cost
• The sequencing of “related” jobs
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
• Relaxation Methods for Pure and Mixed Integer Programming Problems
• A hybrid algorithm for the one machine sequencing problem to minimize total tardiness
• On the N-Job One-Machine, Sequence-Independent Scheduling Problem with Tardiness Penalties: A Branch-Bound Solution
• The traveling-salesman problem and minimum spanning trees: Part II