A Fully Polynomial Time Approximation Scheme for Parallel Machine Scheduling with Machine Availability Constraint

Project Details


This research considers a parallel machine scheduling problem to minimize total completion time, each machine with a specified maintenance time. Mellouli et al. (2009) proposed a pseudo-polynomial dynamic programming algorithm to solve this problem. To the best of our knowledge, no researches have proposed fully polynomial-time approximation schemes (FPTAS) for the problem. Schuurman and Woeginger (2011) and Woeginger (2000) pointed out that to ensure the existence of FPTAS based on the trimming-the-state-space approach, the scheduling problem and its dynamic programming algorithm must have some properties and meet certain conditions. According to our preliminary study, both the scheduling problem and the dynamic programming algorithm proposed by Mellouli et al. meet these properties and conditions. Therefore, in this research, we try to apply the trimming-the-state-space approach to reduce the state space at each phase of dynamic program and to find a ρ-approximation algorithm, where ρ = 1 + ε for any ε> 0. The state space of solution in each phase of the dynamic programming algorithm is reduced, and the propagation of error is limited. The computational time complexity of the proposed FPTAS algorithm is polynomial of input size and 1/ε.
Effective start/end date1/08/1831/07/19

UN Sustainable Development Goals

In 2015, UN member states agreed to 17 global Sustainable Development Goals (SDGs) to end poverty, protect the planet and ensure prosperity for all. This project contributes towards the following SDG(s):

  • SDG 11 - Sustainable Cities and Communities
  • SDG 17 - Partnerships for the Goals


  • Parallel machine scheduling with machine availability constraint
  • Approximation scheme
  • Pseudo-polynomial dynamic programming algorithms
  • Fully polynomial-time approximation scheme
  • Trimming-the-state-space approach


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.