Fast Approximation for Scheduling One Machine
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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-09-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/8/9/1524 |
| _version_ | 1827706717500080128 |
|---|---|
| author | Federico Alonso-Pecina José Alberto Hernández José Maria Sigarreta Nodari Vakhania |
| author_facet | Federico Alonso-Pecina José Alberto Hernández José Maria Sigarreta Nodari Vakhania |
| author_sort | Federico Alonso-Pecina |
| collection | DOAJ |
| description | 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 <inline-formula><math display="inline"><semantics><mrow><mn>1</mn><mo>+</mo><mn>1</mn><mo>/</mo><mi>κ</mi></mrow></semantics></math></inline-formula> for a generated solution if there are <inline-formula><math display="inline"><semantics><mi>κ</mi></semantics></math></inline-formula> 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 <inline-formula><math display="inline"><semantics><mi>κ</mi></semantics></math></inline-formula> 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 <inline-formula><math display="inline"><semantics><mi>κ</mi></semantics></math></inline-formula> becomes sufficiently large so that the approximation factor which the algorithm guarantees becomes better than that provided by the earlier known approximation algorithms. |
| first_indexed | 2024-03-10T16:30:25Z |
| format | Article |
| id | doaj.art-1f54917a9b114933b7f3ca75e088b809 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T16:30:25Z |
| publishDate | 2020-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-1f54917a9b114933b7f3ca75e088b8092023-11-20T12:50:25ZengMDPI AGMathematics2227-73902020-09-0189152410.3390/math8091524Fast Approximation for Scheduling One MachineFederico Alonso-Pecina0José Alberto Hernández1José Maria Sigarreta2Nodari Vakhania3Faculty of Account, Administration and Informatics, Universidad Autónoma del Estado de Morelos, Cuernavaca 62209, MexicoFaculty of Account, Administration and Informatics, Universidad Autónoma del Estado de Morelos, Cuernavaca 62209, MexicoFacultad de Matemáticas UAGro, Universidad Autónoma de Guerrero, Acapulco 39650, MexicoCentro de Investigación en Ciencias, UAEMor, On sabbatical leave at Facultad de Matemáticas UAGro, Universidad Autónoma de Guerrero, Acapulco 39650, MexicoWe 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 <inline-formula><math display="inline"><semantics><mrow><mn>1</mn><mo>+</mo><mn>1</mn><mo>/</mo><mi>κ</mi></mrow></semantics></math></inline-formula> for a generated solution if there are <inline-formula><math display="inline"><semantics><mi>κ</mi></semantics></math></inline-formula> 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 <inline-formula><math display="inline"><semantics><mi>κ</mi></semantics></math></inline-formula> 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 <inline-formula><math display="inline"><semantics><mi>κ</mi></semantics></math></inline-formula> becomes sufficiently large so that the approximation factor which the algorithm guarantees becomes better than that provided by the earlier known approximation algorithms.https://www.mdpi.com/2227-7390/8/9/1524scheduling algorithmenumerationapproximationrelease timedue-datedelivery time |
| spellingShingle | Federico Alonso-Pecina José Alberto Hernández José Maria Sigarreta Nodari Vakhania Fast Approximation for Scheduling One Machine Mathematics scheduling algorithm enumeration approximation release time due-date delivery time |
| title | Fast Approximation for Scheduling One Machine |
| title_full | Fast Approximation for Scheduling One Machine |
| title_fullStr | Fast Approximation for Scheduling One Machine |
| title_full_unstemmed | Fast Approximation for Scheduling One Machine |
| title_short | Fast Approximation for Scheduling One Machine |
| title_sort | fast approximation for scheduling one machine |
| topic | scheduling algorithm enumeration approximation release time due-date delivery time |
| url | https://www.mdpi.com/2227-7390/8/9/1524 |
| work_keys_str_mv | AT federicoalonsopecina fastapproximationforschedulingonemachine AT josealbertohernandez fastapproximationforschedulingonemachine AT josemariasigarreta fastapproximationforschedulingonemachine AT nodarivakhania fastapproximationforschedulingonemachine |