Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
Operations ResearchPublished 1 December 1980
Chris N. Potts
Citations200
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
The analysis of some heuristics or approximation algorithms which never deviate by more than 100% from the optimum is focused on.
Abstract
The single machine sequencing problem is considered in which each job has a release date, a processing time and a delivery time. The objective is to find a sequence of jobs which minimizes the time by which all jobs are delivered. A heuristic is presented which never deviates by more than 50% from the optimum.
Keywords
Engineering
Operations ResearchOn Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness
232 Citations1975Graham McMahon, Michaël Florian
An algorithm is developed for sequencing jobs on a single processor in order to minimize maximum lateness, subject to ready times and due dates, that has the unusual feature that a complete solution is associated with each node of the enumeration tree.
Operations ResearchPerformance Guarantees for Scheduling Algorithms
130 Citations1978M. R. Garey, Ronald Graham +1 more
This paper presents an introduction to this approach to scheduling by describing its application to a well-known multiprocessor scheduling model and illustrating the variety of algorithms and results that are possible.
Management ScienceWorst-Case Analysis of Heuristic Algorithms
126 Citations1980Marshall L. Fisher
In this paper the basic ground rules of worst-case analysis of heuristics are reviewed, and a large variety of the existing types ofworst-case results are described in terms of the knapsack problem.