Fast Approximation for Scheduling One Machine

Federico Alonso-Pecina, José Alberto Hernández, José Maria Sigarreta and Nodari Vakhania
Additional contact information
Federico Alonso-Pecina: Faculty of Account, Administration and Informatics, Universidad Autónoma del Estado de Morelos, Cuernavaca 62209, Mexico
José Alberto Hernández: Faculty of Account, Administration and Informatics, Universidad Autónoma del Estado de Morelos, Cuernavaca 62209, Mexico
José Maria Sigarreta: Facultad de Matemáticas UAGro, Universidad Autónoma de Guerrero, Acapulco 39650, Mexico
Nodari Vakhania: Centro de Investigación en Ciencias, UAEMor, On sabbatical leave at Facultad de Matemáticas UAGro, Universidad Autónoma de Guerrero, Acapulco 39650, Mexico

Mathematics, 2020, vol. 8, issue 9, 1-18

Abstract: We propose an approximation algorithm for scheduling jobs with release and delivery times on a single machine with the objective to minimize the makespan. The algorithm is based on an implicit enumeration of the set of complete solutions in a search tree. By analyzing specific structural properties of the solutions created in each branch of the solution tree, a certain approximation factor of each solution from that branch is calculated. Our algorithm guarantees approximation factor 1 + 1 / κ for a generated solution if there are κ jobs with a specified property in that solution (typically, the longer the length of the path from the root to the node representing that solution in the solution tree, the larger the κ value). We have carried out an extensive computational study to verify the practical performance of our algorithm and the effectiveness of the approximation factor provided by us. While our problem instances are generated randomly, we have discarded a considerable number of the instances, ones which were already solved optimally by the earlier known dominance rules. For the vast majority of the tested problem instances, within a short running time of our algorithm parameter κ becomes sufficiently large so that the approximation factor which the algorithm guarantees becomes better than that provided by the earlier known approximation algorithms.

Keywords: scheduling algorithm; enumeration; approximation; release time; due-date; delivery time; single-machine (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/9/1524/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/9/1524/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:9:p:1524-:d:409981

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().