Approximation Schemes for Parallel Machine Scheduling Problems

Project Details


In this research, two parallel machine scheduling problems with a common due date havingthe aim of minimizing total weighted tardiness are considered. These two problems are!"|$% = $| '%(% and !"|$% = $| '%(% . Tuong, Soukhal, and Billaut (2009) have providedpseudo-polynomial dynamic programming algorithms for the problems that requireO "#$%&'#()#*% ++ for !"|$% = $| '%(% and O "#$%&'($)*$+& for !" #$ = # &$'$ with!" = $%"%&' which can be extremely large. To the best of our knowledge, there is no publishedresearch which carry on approximation algorithm for these two problems.2It is shown that several researchers have successfully applied structuring the input approach toget a fully polynomial-time approximation scheme, or an FPTAS for their problems when the exactoptimal solution for these problems are based on dynamic programming formulations. In thisresearch, we will apply structuring the input approach to develop two ρ - approximation algorithmsfor the two scheduling problems stated above with ρ = 1 + ε for any ε > 0 and the running timewhich is polynomial with respect to both input size and 1/ε.
Effective start/end date1/08/1731/07/18


  • Parallel machine scheduling
  • Approximation scheme
  • Pseudo-polynomial dynamicprogramming algorithms
  • Fully polynomial-time approximation scheme
  • Structuring the inputtechnique


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.