Optimal Sequencing of a Single Machine Subject to Precedence Constraints

DOI10.1287/mnsc.19.5.544zbMath0254.90039OpenAlexW2115299891MaRDI QIDQ5668250

Eugene L. Lawler

Publication date: 1973

Published in: Management Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/mnsc.19.5.544

Mathematics Subject Classification ID

Integer programming (90C10)

Related Items

Scheduling with fuzzy delays and fuzzy precedences. ⋮ Integrated production and outbound distribution scheduling problems with job release dates and deadlines ⋮ Rescheduling problems with allowing for the unexpected new jobs arrival ⋮ Single-machine bicriterion group scheduling with deteriorating setup times and job processing times ⋮ Single machine scheduling problems with uncertain parameters and the OWA criterion ⋮ Scheduling problems with a weight-modifying-activity ⋮ On the flexibility of a decision theory-based heuristic for single machine scheduling ⋮ Minimizing the number of late jobs in a stochastic setting using a chance constraint ⋮ Parallel-machine scheduling with release dates and rejection ⋮ Lawler's minmax cost algorithm: optimality conditions and uncertainty ⋮ Exact algorithms for single-machine scheduling with time windows and precedence constraints ⋮ Single machine scheduling with two competing agents and equal job processing times ⋮ Single machine group scheduling with ordered criteria ⋮ Optimal restricted due date assignment in scheduling ⋮ Single machine scheduling with rejection and generalized parameters ⋮ Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness ⋮ Single machine scheduling problem with two synergetic agents and piece-rate maintenance ⋮ Minimizing total weighted late work on a single-machine with non-availability intervals ⋮ Single-machine time-dependent scheduling problems with fixed rate-modifying activities and resumable jobs ⋮ Sufficient conditions for the optimality of the greedy algorithm in greedoids ⋮ Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties ⋮ Chance-constrained model for uncertain job shop scheduling problem ⋮ An \(O(n \log^ 2\,n)\) algorithm for the maximum weighted tardiness problem ⋮ An algorithm for single machine sequencing with release dates to minimize maximum cost ⋮ Tradeoff solutions in single machine production scheduling for minimizing flow time and maximum penalty ⋮ k-optimal solution sets for some polynomially solvable scheduling problems ⋮ A 2-OPT procedure to reduce total inspection time in a serial inspection process ⋮ Lawler's minmax cost problem under uncertainty ⋮ Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time ⋮ Multiple and bicriteria scheduling: A literature survey ⋮ A constraint programming approach for a batch processing problem with non-identical job sizes ⋮ Scheduling problems with partially ordered jobs ⋮ Minimizing makespan on a single machine with release dates and inventory constraints ⋮ Minimizing maximum cost for a single machine under uncertainty of processing times ⋮ Pareto minimizing total completion time and maximum cost with positional due indices ⋮ A survey on offline scheduling with rejection ⋮ A note on reverse scheduling with maximum lateness objective ⋮ Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices ⋮ Sequencing with general precedence constraints ⋮ On the measurement of complexity in activity networks ⋮ Algorithms and complexity analysis for robust single-machine scheduling problems ⋮ Scheduling two agents on uniform parallel machines with~makespan and cost functions ⋮ The Pareto-optimal set of the NP-hard problem of minimization of the maximum lateness for a single machine ⋮ Probabilistic single processor scheduling ⋮ A faster algorithm for the maximum weighted tardiness problem ⋮ A bicriterion approach to time/cost trade-offs in sequencing ⋮ Optimal assignment of slack due-dates and sequencing in a single-machine shop ⋮ Single machine bicriteria scheduling with equal-length jobs to minimize total weighted completion time and maximum cost ⋮ Minimizing functions of infeasibilities in a two-machine flow shop ⋮ On the complexity of generalized due date scheduling problems ⋮ Performance guarantees for a scheduling problem with common stepwise job payoffs ⋮ A note: Maximizing the weighted number of just-in-time jobs on a proportionate flowshop ⋮ A note: minimizing maximum earliness on a proportionate flowshop ⋮ Optimization of inland shipping. A polynomial time algorithm for the single-ship single-lock optimization problem ⋮ Pareto optimization scheduling with two competing agents to minimize the number of tardy jobs and the maximum cost ⋮ Exact algorithms for the solution of the grey pattern quadratic assignment problem ⋮ Complexity of single machine scheduling problems under scenario-based uncertainty ⋮ Finding efficient make-to-order production and batch delivery schedules ⋮ A metric approach for scheduling problems with minimizing the maximum penalty ⋮ Applications of a semi-dynamic convex hull algorithm ⋮ Bi-criteria Pareto-scheduling on a single machine with due indices and precedence constraints ⋮ Minimizing the number of tardy jobs in single machine sequencing ⋮ Scheduling partially ordered jobs faster than \(2^n\) ⋮ Scheduling with bully selfish jobs ⋮ Single-machine scheduling under the job rejection constraint ⋮ Single machine scheduling with precedence constraints and positionally dependent processing times ⋮ A possibilistic approach to sequencing problems with fuzzy parameters ⋮ Single machine scheduling to minimize total weighted tardiness ⋮ Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints ⋮ Single machine batch scheduling with two non-disjoint agents and splitable jobs ⋮ A note on Pareto minimizing total completion time and maximum cost ⋮ Ideal schedules in parallel machine settings ⋮ Single-machine scheduling with an external resource ⋮ Minimizing total late work on a single machine with generalized due-dates ⋮ Single-machine hierarchical scheduling with release dates and preemption to minimize the total completion time and a regular criterion ⋮ Single-machine scheduling with release times, deadlines, setup times, and rejection ⋮ Four solution techniques for a general one machine scheduling problem. A comparative study ⋮ Risk-averse single machine scheduling: complexity and approximation ⋮ Integrated scheduling of production and distribution with release dates and capacitated deliveries ⋮ Solving scheduling and location problems in the plane simultaneously ⋮ Two-agent scheduling on uniform parallel machines with min-max criteria ⋮ Isomorphic scheduling problems ⋮ Bicriterion scheduling of identical processing time jobs by uniform processors ⋮ A review of four decades of time-dependent scheduling: main results, new topics, and open problems ⋮ Unbounded serial-batching scheduling on hierarchical optimization ⋮ Bicriterion scheduling with group technology and deterioration effect ⋮ Scheduling inverse trees under the communication model of the LogP-machine ⋮ The counting complexity of a simple scheduling problem ⋮ Single machine scheduling with release dates and rejection ⋮ Balancing assembly lines with variable parallel workplaces: problem definition and effective solution procedure ⋮ Scheduling with release dates and preemption to minimize multiple max-form objective functions ⋮ Improved polynomial algorithms for robust bottleneck problems with interval data ⋮ Effective optimization methods for single-machine scheduling (survey) ⋮ Logic-based Benders decomposition for scheduling a batching machine ⋮ Optimal assignment of slack due-date and sequencing in a single machine shop ⋮ A note on generalizing the maximum lateness criterion for scheduling ⋮ Mathematical programming formulations for machine scheduling: A survey ⋮ An optimal scheduling algorithm for preemptable real-time tasks ⋮ Approximability of scheduling problems with resource consuming jobs ⋮ On two single machine scheduling problems with fuzzy processing times and fuzzy due dates ⋮ Taking advantage of symmetry in some quadratic assignment problems ⋮ SOME GENERAL PROPERTIES OF A FUZZY SINGLE MACHINE SCHEDULING PROBLEM ⋮ An algorithmic characterization of antimatroids ⋮ Time complexity of single machine scheduling with stochastic precedence constraints ⋮ Algorithms for single-machine scheduling with stochastic outtree precedence relations to minimize expected weighted flow time or maximum expected lateness ⋮ Optimal assignment of NOP due-dates and sequencing in a single machine shop ⋮ An exact framework for the discrete parallel machine scheduling location problem ⋮ Algorithms for single machine scheduling problem with release dates and submodular penalties ⋮ Heuristic and exact algorithms for single-machine scheduling problems with general truncated learning effects ⋮ Two-agent single-machine scheduling with release dates to minimize the makespan ⋮ Point-to-point and milk run delivery scheduling: models, complexity results, and algorithms based on Benders decomposition ⋮ Online Single Machine Scheduling to Minimize the Maximum Starting Time ⋮ A state-of-the-art survey on multi-scenario scheduling ⋮ A note on lot scheduling on a single machine to minimize maximum weighted tardiness ⋮ Order acceptance and scheduling with delivery under generalized parameters ⋮ Min-max relative regret for scheduling to minimize maximum lateness ⋮ Faster algorithms for bicriteria scheduling of identical jobs on uniform machines ⋮ Maximum cost scheduling of jobs with mixed variable processing times and \(k\)-partite precedence constraints ⋮ Approximations for the two-machine cross-docking flow shop problem ⋮ Scheduling deteriorating jobs on a single machine to minimize the maximum processing times ⋮ Heuristics for minimizing maximum lateness on a single machine with family-dependent set-up times ⋮ Multi-agent scheduling on a single machine with max-form criteria ⋮ Sequencing jobs on a single machine: A neural network approach ⋮ Multi-agent single machine scheduling ⋮ Stochastic scheduling to minimize expected maximum lateness ⋮ Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times ⋮ Group Scheduling with Two Competing Agents on a Single Machine ⋮ The complexity of machine scheduling for stability with a single disrupted job ⋮ Characterizations of polygreedoids and poly-antimatroids by greedy algorithms ⋮ Minimizing maximal regret in the single machine sequencing problem with maximum lateness criterion ⋮ Scheduling with tails and deadlines ⋮ Scheduling in a contaminated area: a model and polynomial algorithms ⋮ Applications of a semi-dynamic convex hull algorithm ⋮ A branch and bound algorithm for the minimum storage-time sequencing problem ⋮ A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems ⋮ Single Machine General Maximum Cost Problem with Parallel-Chain Precedence Constraints ⋮ Evaluation of a new decision-aid parameter for job shop scheduling under uncertainties ⋮ Unnamed Item ⋮ Scheduling orders for multiple product types with due date related objectives