A time indexed formulation of non-preemptive single machine scheduling problems
Mathematical ProgrammingPublished 1 February 1992
Jorge Pinho de Sousa, Laurence A. Wolsey
Citations235
SJR quartileQ1
SJR score1.73
SNIP2.20
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work considers the formulation of non-preemptive single machine scheduling problems using time-indexed variables and derives a variety of valid inequalities, and shows the role of constraint aggregation and the knapsack problem with generalised upper bound constraints as a way of generating such inequalities.
Abstract
We consider the formulation of non-preemptive single machine scheduling problems using time-indexed variables. This approach leads to verv large models, but gives better lower bounds than other mixed integer programming formulations. We derive a variety of valid inequalities, and show the role of constraint aggregation and the knapsack problem with generalised upper bound constraints as a way of generating such inequalities. A cutting plane/branch-and-bound algorithm based on these inequalities has been implemented. Computational experience on small problems with 20/30 jobs and various constraints and objective functions is presented.
Keywords
Engineering
Annals of discrete mathematicsComplexity of Machine Scheduling Problems
2,148 Citations1977Jan Karel Lenstra, A. H. G. Rinnooy Kan +1 more
A classification of scheduling problems on single, different and identical machines is given and NP-completeness is established for a large number of other machine scheduling problems.
Management ScienceThe Shifting Bottleneck Procedure for Job Shop Scheduling
1,600 Citations1988Joseph Adams, Egon Balas +1 more
An approximation method for solving the minimum makespan problem of job shop scheduling by sequences the machines one by one, successively, taking each time the machine identified as a bottleneck among the machines not yet sequenced.
Management ScienceMultiproject Scheduling with Limited Resources: A Zero-One Programming Approach
750 Citations1969A. Alan B. Pritsker, Lawrence J. Waiters +1 more
A zero-one 0-1 linear programming formulation of multiproject and job-shop scheduling problems is presented that is more general and computationally tractable than other known formulations.
European Journal of Operational ResearchThe one-machine sequencing problem
524 Citations1982Jacques Carlier
Management ScienceResource-Constrained Project Scheduling with Time-Resource Tradeoffs: The Nonpreemptive Case
454 Citations1982F. Brian Talbot
Computational results indicate that the procedures provide cost-effective optimal solutions for small problems and good heuristic solutions for larger problems, while simultaneously taking into account a variety of constraint types.
Mathematical ProgrammingFacets of the knapsack polytope
393 Citations1975Egon Balas
A necessary and sufficient condition is given for an inequality with coefficients 0 or 1 to define a facet of the knapsack polytope, i.e., of the convex hull of 0–1 points satisfying a given linear inequality.
European Journal of Operational ResearchProject scheduling with resource constraints: A branch and bound approach
366 Citations1987Nicos Christofides, Ramón Álvarez-Valdés +1 more
A branch and bound algorithm for project scheduling with resource constraints based on the idea of using disjunctive arcs for resolving conflicts that are created whenever sets of activities have to be scheduled whose total resource requirements exceed the resource availabilities in some periods is described.
Recent Developments in Deterministic Sequencing and Scheduling: A Survey
318 Citations1982Eugene L. Lawler, Jan Karel Lenstra +1 more
The state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory are surveyed.
Operations ResearchThe Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
290 Citations1978Jean‐Claude Picard, Maurice Queyranne
The optimization method described here combines finding shortest paths in an associated multipartite network with subgradient optimization and some branch-and-bound enumeration and gives computational results for the weighted tardiness problem.
Discrete Applied MathematicsFormulating the single machine sequencing problem with release dates as a mixed integer program
240 Citations1990Martin Dyer, Laurence A. Wolsey
A hierarchy of relaxations obtained by combining enumeration of initial sequences with Smith's rule can be formulated as a linear programming problem in an enlarged space of variables and new valid inequalities for the problem are obtained.
Operations ResearchMinimizing Total Costs in One-Machine Scheduling
206 Citations1975A. H. G. Rinnooy Kan, B.J. Lageweg +1 more
A new algorithm is presented for a general cost function for a continuously available machine that can handle only one job at a time to find a schedule that minimizes total costs.
Recent Results in the Theory of Machine Scheduling
149 Citations1983E. L. Lawler
The state of the art of deterministic machine scheduling is reviewed, and emphasis is placed on efficient, i.
Management ScienceScheduling a Project to Maximize Its Present Value: A Zero-One Programming Approach
147 Citations1977Robert H. Doersch, J. Herbert Patterson
Discrete Applied MathematicsAn algorithm for single machine sequencing with release dates to minimize total weighted completion time
136 Citations1983A.M.A. Hariri, Chris N. Potts
The computational results indicate that the version of the lower bound using improved constraints is superior to the original version, which includes several dominance rules, and is tested on problems with up to fifty jobs.
Journal of the Operational Research SocietyDynamic Programming State-Space Relaxation for Single-Machine Scheduling
136 Citations1988Tariq S. Abdul-Razaq, Chris N. Potts
The problem of sequencing jobs on a single machine to minimize total cost is considered, and it is shown that the dynamic programming formulation can be relaxed by mapping the state-space onto a smaller state- space and performing the recursion on this smallerstate-space, thereby giving a lower bound.
Discrete Applied MathematicsValid inequalities for 0–1 knapsacks and mips with generalised upper bound constraints
101 Citations1990Laurence A. Wolsey
It is shown that the inequalities are “strong” by showing that in one special case, they suffice to describe the convex hull of solutions, and for other models it is possible to obtain violated inequalities by using constraint aggregation followed by the above separation procedure.
DSpace@MIT (Massachusetts Institute of Technology)On the n-job, one-machine, sequence-independent scheduling problem with tardiness penalties: a branch-bound solution
76 Citations2011Joel Shwimer
Operations ResearchMinimizing Weighted Completion Times with Deadlines
74 Citations1985Marc E. Posner
A one-machine scheduling problem whose objective is to minimize the weighted sum of completion times, subject to deadline constraints is examined, and current known theory is synthesized and extended, and precedence relations between jobs are derived.
European Journal of Operational ResearchAn algorithm for single machine sequencing with deadlines to minimize total weighted completion time
68 Citations1983Chris N. Potts, Luk N. Van Wassenhove
Management ScienceOn the <i>N</i>-Job One-Machine, Sequence-Independent Scheduling Problem with Tardiness Penalties: A Branch-Bound Solution
53 Citations1972Joel Shwimer
An efficient branch-bound algorithm is presented for solving the n-job, sequence-independent, single machine scheduling problem where the goal is to minimize the total penalty costs resulting from tardiness of jobs.
European Journal of Operational ResearchSingle machine scheduling to minimize weighted sum of completion times with secondary criterion — A branch and bound approach
45 Citations1980Saumya Bansal
Journal of Optimization Theory and ApplicationsA mixed integer programming model for scheduling orders in a steel mill
38 Citations1974C N Redwine, David A. Wismer
European Journal of Operational ResearchTeaching operational research to first year undergraduates: Experience at Lancaster
3 Citations1980Graham K. Rand
The content of the first year Operational Research course, which concentrates on the methodology of OR, is described and various statistics presented to show the growing importance of OR as a course within the University and Lancaster as a producer of graduates with a first degree in OR.