Volume 19, Issue 4 (12-2022)
jor 2022, 19(4): 17-36 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Seifaddini M. Differential Approximation Schemes for Scheduling Problems on Single machine with Availability Constraint. jor 2022; 19 (4) :17-36
URL: http://jamlu.liau.ac.ir/article-1-2080-en.html
URL: http://jamlu.liau.ac.ir/article-1-2080-en.html
Department of Computer Science, University of Guilan, Guilan, Iran
Abstract: (584 Views)
Scheduling problems have been considered by researchers from different aspects, and it has been widely addressed in the literature. Most scheduling problems, and almost all that arise in real-world applications, are NP-hard, therefore finding a proper and feasible solution, a solution that is performed in a reasonable time (polynomial time), is difficult. Approximation scheme, among different methods, is one approach that can overcome difficulties. Polynomial-time approximation and differential approximation schemes are categorized as approximation approaches based on comparing the proposed algorithm with optimum and worst-case solutions.
As the first attempt, the paper investigates differential approximation schemes for the minimization of maximum delivery time. In this paper, the main methods and tools for proving the existence of an approximation scheme are presented. To do so, a differential approximation scheme is proposed by employing a polynomial-time approximation scheme (PTAS). The paper also reviews efficient approximation schemes on single machine problems with objective functions minimization of maximum delivery time, and minimizing the total weighted completion time. Also, in this paper, using the polynomial time approximation scheme (PTAS), a differential approximation scheme has been studied for the problem of minimizing the maximum delivery time of works, which has not been investigated so far.
As the first attempt, the paper investigates differential approximation schemes for the minimization of maximum delivery time. In this paper, the main methods and tools for proving the existence of an approximation scheme are presented. To do so, a differential approximation scheme is proposed by employing a polynomial-time approximation scheme (PTAS). The paper also reviews efficient approximation schemes on single machine problems with objective functions minimization of maximum delivery time, and minimizing the total weighted completion time. Also, in this paper, using the polynomial time approximation scheme (PTAS), a differential approximation scheme has been studied for the problem of minimizing the maximum delivery time of works, which has not been investigated so far.
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
