Department of Computer Science, University of Guilan, Guilan, Iran
Abstract: (651 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.
Type of Study:
Review paper |
Subject:
Special Received: 2021/12/31 | Accepted: 2022/06/6