Total Tardiness Minimization in a Single-Machine with Periodical Resource Constraints
In this paper we introduce a variant of the single machine considering resource restriction per period. The objective function to be minimized is the total tardiness. We proposed an integer linear programming modeling based on a bin packing formulation. In view of the NP-hardness of the introduced...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Universitas Andalas
2022-12-01
|
| Series: | Jurnal Optimasi Sistem Industri |
| Subjects: | |
| Online Access: | https://josi.ft.unand.ac.id/index.php/josi/article/view/117 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850070154440867840 |
|---|---|
| author | Bruno Prata Levi Ribeiro de Abreu Marcelo Seido Nagano |
| author_facet | Bruno Prata Levi Ribeiro de Abreu Marcelo Seido Nagano |
| author_sort | Bruno Prata |
| collection | DOAJ |
| description |
In this paper we introduce a variant of the single machine considering resource restriction per period. The objective function to be minimized is the total tardiness. We proposed an integer linear programming modeling based on a bin packing formulation. In view of the NP-hardness of the introduced variant, heuristic algorithms are required to find high-quality solutions within an admissible computation times. In this sense, we present a new hybrid matheuristic called Relax-and-Fix with Variable Fixing Search (RFVFS). This innovative solution approach combines the relax-and-fix algorithm and a strategy for the fixation of decision variables based on the concept of the variable neighborhood search metaheuristic. As statistical indicators to evaluate the solution procedures under comparison, we employ the Average Relative Deviation Index (ARDI) and the Success Rate (SR). We performed extensive computational experimentation with a testbed composed by 450 proposed test problems. Considering the results for the number of jobs, the RFVFS returned ARDI and SR values of 35.6% and 41.3%, respectively. Our proposal outperformed the best solution approach available for a closely-related problem with statistical significance.
|
| format | Article |
| id | doaj-art-80e441b1ac9d458197ea6f7f3f00bda2 |
| institution | DOAJ |
| issn | 2088-4842 2442-8795 |
| language | English |
| publishDate | 2022-12-01 |
| publisher | Universitas Andalas |
| record_format | Article |
| series | Jurnal Optimasi Sistem Industri |
| spelling | doaj-art-80e441b1ac9d458197ea6f7f3f00bda22025-08-20T02:47:36ZengUniversitas AndalasJurnal Optimasi Sistem Industri2088-48422442-87952022-12-0121210.25077/josi.v21.n2.p97-105.2022Total Tardiness Minimization in a Single-Machine with Periodical Resource ConstraintsBruno Prata0Levi Ribeiro de Abreu1Marcelo Seido Nagano2University of CearaUniversity of Sao PauloUniversity of Sao Paulo In this paper we introduce a variant of the single machine considering resource restriction per period. The objective function to be minimized is the total tardiness. We proposed an integer linear programming modeling based on a bin packing formulation. In view of the NP-hardness of the introduced variant, heuristic algorithms are required to find high-quality solutions within an admissible computation times. In this sense, we present a new hybrid matheuristic called Relax-and-Fix with Variable Fixing Search (RFVFS). This innovative solution approach combines the relax-and-fix algorithm and a strategy for the fixation of decision variables based on the concept of the variable neighborhood search metaheuristic. As statistical indicators to evaluate the solution procedures under comparison, we employ the Average Relative Deviation Index (ARDI) and the Success Rate (SR). We performed extensive computational experimentation with a testbed composed by 450 proposed test problems. Considering the results for the number of jobs, the RFVFS returned ARDI and SR values of 35.6% and 41.3%, respectively. Our proposal outperformed the best solution approach available for a closely-related problem with statistical significance. https://josi.ft.unand.ac.id/index.php/josi/article/view/117Production SequencingCombinatorial OptimizationMatheuristicsResource Consumption |
| spellingShingle | Bruno Prata Levi Ribeiro de Abreu Marcelo Seido Nagano Total Tardiness Minimization in a Single-Machine with Periodical Resource Constraints Jurnal Optimasi Sistem Industri Production Sequencing Combinatorial Optimization Matheuristics Resource Consumption |
| title | Total Tardiness Minimization in a Single-Machine with Periodical Resource Constraints |
| title_full | Total Tardiness Minimization in a Single-Machine with Periodical Resource Constraints |
| title_fullStr | Total Tardiness Minimization in a Single-Machine with Periodical Resource Constraints |
| title_full_unstemmed | Total Tardiness Minimization in a Single-Machine with Periodical Resource Constraints |
| title_short | Total Tardiness Minimization in a Single-Machine with Periodical Resource Constraints |
| title_sort | total tardiness minimization in a single machine with periodical resource constraints |
| topic | Production Sequencing Combinatorial Optimization Matheuristics Resource Consumption |
| url | https://josi.ft.unand.ac.id/index.php/josi/article/view/117 |
| work_keys_str_mv | AT brunoprata totaltardinessminimizationinasinglemachinewithperiodicalresourceconstraints AT leviribeirodeabreu totaltardinessminimizationinasinglemachinewithperiodicalresourceconstraints AT marceloseidonagano totaltardinessminimizationinasinglemachinewithperiodicalresourceconstraints |