Claim Missing Document
Check
Articles

Found 2 Documents
Search

Total Tardiness Minimization in a Single-Machine with Periodical Resource Constraints Bruno Prata; Levi Ribeiro Abreu; Marcelo Seido Nagano
Jurnal Optimasi Sistem Industri Vol. 21 No. 2 (2022): Published in November 2022
Publisher : The Industrial Engineering Department of Engineering Faculty at Universitas Andalas

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.25077/josi.v21.n2.p97-105.2022

Abstract

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.
Total Tardiness Minimization in a Single-Machine with Periodical Resource Constraints Bruno Prata; Levi Ribeiro de Abreu; Marcelo Seido Nagano
Jurnal Optimasi Sistem Industri Vol. 21 No. 2 (2022): Published in October 2022
Publisher : The Industrial Engineering Department of Engineering Faculty at Universitas Andalas

Show Abstract | Download Original | Original Source | Check in Google Scholar | Full PDF (616.904 KB) | DOI: 10.25077/josi.v21.n2.p97-105.2022

Abstract

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.