Adaptive scheduling algorithm based on mixed graph model

Access Full Text

Adaptive scheduling algorithm based on mixed graph model

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IEE Proceedings - Control Theory and Applications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© IEE
Published

This paper deals with an adaptive approach for scheduling problems. The main idea is to produce, for a class of similar problems, a special heuristic rule which is successful for problems of this class. It is realised by ‘tuning’ the parameters of the algorithm while ‘learning’ on the peculiarities of considering a class of problems. Once trained on the sample problems (in our experiments a well-known test problem with 10 jobs and 10 machines has been considered), the adaptive algorithm solves ‘close’ problems better than a branch and bound algorithm with a time limit (both in running time and in accuracy of the constructed schedule) and better than the 25 heuristics (in accuracy) used in the learning stage. However, the adaptive algorithm is unable to perform better than the branch and bound algorithm with a time limit for such scheduling problems, which are not sufficiently close to the sample problem.

Inspec keywords: scheduling; graph theory; computational complexity

Other keywords: tuning; adaptive algorithm; branch and bound algorithm; adaptive scheduling algorithm; mixed graph model

Subjects: Systems theory applications; Combinatorial mathematics; Combinatorial mathematics; Production management; Systems theory applications in industry; Computational complexity

References

    1. 1)
      • Sotskov, Yu.N.: ‘Constructing an optimal makespanschedule forprocessing jobsby sequential machines’, Institute of Engineering Cybernetics of Academy of Sciencesof Belarus, 1981, pp. 28–34 (in Russian).
    2. 2)
      • V.S. Tanaev , Yu.N. Sotskov , V.A. Strusevich . (1994) Scheduling theory. Multistage systems.
    3. 3)
      • M.R. Garey , D.S. Johnson . (1979) Computers and intractibility: a guide to the theory of NP-completeness.
    4. 4)
      • E. Balas . Machine sequencing via disjunctive graphs: an implicit enumeration algorithm. Oper. Res. , 941 - 957
    5. 5)
      • J.F. Muth , G.L. Thompson . (1963) Industrial scheduling.
    6. 6)
      • R. Haupt . A survey of priority rule-based scheduling. OR Spektrum , 278 - 285
    7. 7)
      • Sotskov, Yu.N., Shakhlevich, N.V.: `An adaptive approach in production scheduling based on the mixed graphmodel', 395, Second international conference on Intelligent systems engineering, 1994, Technical University of Hamburg–HarburgGermany, p. 413–418.
    8. 8)
      • Roy, B., Sussmann, B.: `Les problems d'ordonnancement avec contraintes disjonctives', SEMA, 1964, Montrougenote DS, .
    9. 9)
      • W.S. Gere . Heuristics in job shop scheduling. Manage. Sci. , 167 - 190
    10. 10)
      • A.H.G. Rinnooy Kan . (1976) Machine scheduling problems: classification, complexity and computations.
    11. 11)
      • Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: `Sequencing and scheduling: algorithms and complexity', BS-R8909, Report, 1989.
    12. 12)
      • M. Florian , P. Trepant , G. McMahon . An implicit enumeration algorithm for the machine sequencing problem. Manage. Sci. , 782 - 792
    13. 13)
      • S.K. Kim , K.T. Yeo , W.H. Lee . An expert neural network system for dynamic job shop scheduling. Intern. J. Prod. Res. , 1759 - 1773
    14. 14)
      • G.B. McMahon , M. Florian . On scheduling with ready times and due dates to minimize maximum lateness. Oper. Res. , 333 - 349
    15. 15)
      • W. Wang , P. Brunn . (1995) Production scheduling and neural networks.
    16. 16)
      • J.N. Blackstone , D.T. Philips , C.L. Hogg . A state-of-the-art survey of dispatching rules for manufacturing jobshop operations. Intern. J. Prod. Res. , 27 - 45
    17. 17)
      • D.-C. Li , I.-S. She . Using unsupervised learning technologies to induce scheduling knowledgefor FMSs. Intern. J. Prod. Res. , 2187 - 2199
    18. 18)
      • J. Carlier , E. Pinson . An algorithm for solving the job shop problem. Manage. Sci. , 475 - 482
    19. 19)
      • Brucker, P., Jurisch, B., Sievers, B.: `A fast branch and bound algorithm for the job shop scheduling problem', 136, Report, 1991.
    20. 20)
      • S.S. Panwalkar , W. Iskander . A survey of scheduling rules. Oper. Res. , 45 - 61
    21. 21)
      • Yu.N. Sotskov , N.V. Shakhlevich . An adaptive algorithm for minimizing the makespan of processing jobsby sequential machines. Izv. Akad. Nauk SSSR, Tekhn. Kibernet. , 137 - 142
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-cta_19960089
Loading

Related content

content/journals/10.1049/ip-cta_19960089
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading