russian 
english 

 

    Our results for the single machine total tardiness problem

We have proofed that the special case {\bf B-1} of the problem when $d_{max}-d_{min} \leq p_{min}$ is NP-hard in the ordinary sense. We have proposed a polynomial scheme of reduction from NP-complete {\bf Partition Problem} to the special case {\bf B-1} of the problem $1\mid\,\mid\sum T_j$. For this case a pseudo-polynomial algorithm with run time $O(n\sum p_j)$ and exact algorithm for $p_j \notin Z$ have been constructed. Therefore we can decide the {\bf Partition Problem} when parameters are not integer. For the case when $d_1\leq \dots \leq d_n$ and $p_1\geq \dots \geq p_n$ we have constructed algorithms with run times $O(n^2 \sum p_j)$ operations. We have showed that the run time of well known algorithms of W. Szwarc et al., A.A Lazarev, S.Chang et al. for the problem $1\mid\mid\sum T_j$ are exponential for some "hard"\ cases without any "paradoxes". For these cases we have new polynomial and pseudo-polynomial algorithms. We offer a new scheme of instances generation then popular scheme C.N.~Potts and L.N.~Van Wassenhove. Our new {\em hybrid algorithm} has joined qualities of meta-heuristik methods (acceptable complexity, low error) and combinatorial properties (Elimination Rules 1-4). Efficiencies for meta-heuristik algorithm "Ant Colony Optimization" and {\em hybrid algorithm} has been compared. Results of our tests show that the relative error of known algorithm "Ant Colony Optimization" is great than relative error of {\em hybrid algorithm}.




    Papers

  Authors:Lazarev A.A., Gafarov E.R.
  Title:Scheduling Theory. The Total Tardiness Problem.
Journal:
Language:russian
  Authors:Lazarev A.A., Gafarov E.R.
  Title:Special case of the single machine total tardiness problem is NP-hard
Journal:Journal of Computer and System Sciences International, N 3, 2006, p.120-128.
Language:english
  Authors:T. C. E. Cheng, Lazarev A.A., Gafarov E.R.
  Title:A Hybrid Algorithm for the Single-Machine Total Tardiness Problem
Journal:
Language:english
  Authors:Lazarev A.A., Kvarazchelia A.G. , Gafarov E.R.
  Title:Algorithms for the total tardiness problem.
Journal:Doklady AN. in print
Language:russian
  Authors:Lazarev A.A.,Gafarov E.R.
  Title:Graphical approach for solving combinatorial problems.
Journal: 
Language:english


    Rambler's Top100
    Members
    Library
    Problems
    Links
    Courses
    Contacts
    News