Advanced materials research · 2007 · 11 citations · 7 references
ManagementIndustrial EngineeringOperations ManagementOperations ResearchProduction PlanningSchedulingJob SchedulingJob SequencingMachine SchedulingProduction SchedulingResource-constrained SchedulingScheduling TheoryBest ApproximationIndustrial ProductionOptimal DispatchPolynomial-time AlgorithmsRelease DatesRelease Time SchedulingScheduling With Release DatesSingle-machine Scheduling
This paper focuses on the problem of scheduling n jobs with release dates on a single machine in order to minimize the total completion time. Since the problem has been characterized as strongly NP-hard, two heuristics (HR1 and AEO) were proposed for solving the problem in polynomial time. The heuristics were compared with the best approximation algorithm for this problem to date (Best-alpha). Experimental results show that AEO performed better than the Bestalpha algorithm (selected from the literature) when the number of jobs (n) exceeds 5. This observation should prove useful in the operational dispatch of jobs in industrial production settings as well as the service sector.
7
Single Machine Scheduling with Release Dates
Michel X. Goemans, Maurice Queyranne, Andreas S. Schulz et al. · SIAM Journal on Discrete Mathematics · 2002 · 148 citations
Approximation Techniques for Average Completion Time Scheduling
Chandra Chekuri, R. Motwani, B. K. Natarajan et al. · SIAM Journal on Computing · 2001 · 146 citations
Single-machine bicriteria scheduling
J.A. Hoogeveen · TU/e Research Portal · 1992 · 67 citations · Full text
Management, Industrial Engineering, Operations Management +14