Minimizing Weighted Completion Times with Deadlines
Operations ResearchPublished 1 June 1985
Marc E. Posner
Citations74
SJR quartileQ1
SJR score2.56
SNIP1.83
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
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.
Abstract
We examine a one-machine scheduling problem whose objective is to minimize the weighted sum of completion times, subject to deadline constraints. We synthesize and extend current known theory, and derive precedence relations between jobs. These relationships, along with tight new bounding criteria, are incorporated in a branch and bound solution procedure.
Keywords
Computer ScienceEngineering
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.
Operations ResearchOne-Machine Sequencing to Minimize Certain Functions of Job Tardiness
346 Citations1969Hamilton Emmons
It proves theorems that establish the relative order in which pairs of jobs are processed in an optimal schedule; frequently they permit the jobs to be completely ordered, thus solving the problem without any searching.
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.
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.
Finding Some Essential Characteristics of the Feasible Solutions for a Scheduling Problem
72 Citations1976J. Erschler, F. Roubellat +1 more
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
Naval Research Logistics QuarterlyScheduling to minimize the weighted sum of completion times with secondary criteria
57 Citations1976R. N. Burns
A new algorithm is given that converges to a local optimum for both problems and is shown to be incorrect and a counter example is presented.
Operations ResearchTechnical Note—Finding Some Essential Characteristics of the Feasible Solutions for a Scheduling Problem
56 Citations1976J. Erschler, F. Roubellat +1 more
The basic principles enabling one to define essential characteristics of the feasible solutions for a job-shop scheduling problem in which the jobs are constrained by fixed starting times and due dates are presented.
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 the Operations Research Society of JapanON THE USE OF DECOMPOSITION APPROACHES IN A SINGLE MACHINE SCHDULING PROBLEM
13 Citations1982J. George Shanthikumar, John A. Buzacott
The idea of decomposition is extended to permutation to form subsets of relations that do not contain any common variables so that each subset can be treated independently.