Theoretical expectation versus practical performance of Jackson's heuristic
type: Item
instance of: scholarly article
title: Theoretical expectation versus practical performance of Jackson's heuristic
zbMATH Open document ID: 1394.90308
DOI: 10.1155/2015/484671
author: Nodari Vakhania
author: Dante Pérez
author: Lester Carballo
published in: Mathematical Problems in Engineering
publication date: 2018-08-27T00:00:00Z
review text: Summary: A basic 2-approximation heuristic was suggested by Jackson in early 50s last century for scheduling jobs with release times and due dates to minimize the maximum job lateness. The theoretical worst-case bound of 2 helps a little in practice, when the solution quality is important. The quality of the solution delivered by Jackson's heuristic is closely related to the maximum job processing time \(p_{\max}\) that occurs in a given problem instance and with the resultant interference with other jobs that such a long job may cause. We use the relationship of \(p_{\max}\) with the optimal objective value to obtain more accurate approximation ratio, which may drastically outperform the earlier known worst-case ratio of 2. This is proved, in practice, by our computational experiments.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6926458
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2015/484671
OpenAlex ID: W2104014624
Wikidata QID: Q59118707
cites work: Solving Resource-Constrained Network Problems by Implicit Enumeration—Nonpreemptive Case
cites work: Q4198056
cites work: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
cites work: On sequencing with earliest starts and due dates with application to computing bounds for the (n/m/G/Fmax) problem
cites work: Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
cites work: Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better
cites work: On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness
cites work: The one-machine sequencing problem
cites work: A block approach for single-machine scheduling with release dates and due dates
cites work: Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines
cites work: Single-machine scheduling with release times and tails
cites work: Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs
cites work: A study of single-machine scheduling problem to maximize throughput
cites work: Branch less, cut more and minimize the number of late equal-length jobs on identical machines
cites work: Multiprocessor Scheduling of Unit-Time Jobs with Arbitrary Release Times and Deadlines
cites work: A Fast Algorithm for Multiprocessor Scheduling of Unit-Length Jobs
cites work: A better algorithm for sequencing with release and delivery times on identical machines
cites work: An Algorithm for Solving the Job-Shop Problem
cites work: Solving open benchmark instances for the job-shop problem by parallel head-tail adjustments
cites work: Jackson's semi-preemptive scheduling on a single machine
cites work: Improving the preemptive bound for the single machine dynamic maximum lateness problem
cites work: Jackson's pseudo preemptive schedule for the \(Pm/r_i, q_i/C_{\text{max}}\) scheduling problem
cites work: Concurrent operations can be parallelized in scheduling multiprocessor job shop
cites work: Parallel branch-and-bound methods for the job-shop scheduling problem
cites work: Parallel batch scheduling of equal-length jobs with release and due dates
cites work: Minimizing maximum lateness of jobs with naturally bounded job data on a single machine in polynomial time
description: scientific article; zbMATH DE number 6926458