Share Email Print

Proceedings Paper

Job-shop scheduling with a combination of evolutionary and heuristic methods
Author(s): Bela Patkai; Seppo Torvinen
Format Member Price Non-Member Price
PDF $17.00 $21.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

Since almost all of the scheduling problems are NP-hard-- cannot be solved in polynomial time--those companies that need a realistic scheduling system face serious limitations of available methods for finding an optimal schedule, especially if the given environment requires adaptation to dynamic variations. Exact methods do find an optimal schedule, but the size of the problem they can solve is very limited, excluding this way the required scalability. The solution presented in this paper is a simple, multi-pass heuristic method, which aims to avoid the limitations of other well-known formulations. Even though the dispatching rules are fast and provide near-optimal solutions in most cases, they are severely limited in efficiency--especially in case the schedule builder satisfies a significant number of constraints. That is the main motivation for adding a simplified genetic algorithm to the dispatching rules, which--due to its stochastic nature--belongs to heuristic, too. The scheduling problem is of a middle size Finnish factory, throughout the investigations their up-to-date manufacturing data has been used for the sake of realistic calculations.

Paper Details

Date Published: 20 August 1999
PDF: 9 pages
Proc. SPIE 3833, Intelligent Systems in Design and Manufacturing II, (20 August 1999); doi: 10.1117/12.359504
Show Author Affiliations
Bela Patkai, Tampere Univ. of Technology (Finland)
Seppo Torvinen, Tampere Univ. of Technology (Finland)

Published in SPIE Proceedings Vol. 3833:
Intelligent Systems in Design and Manufacturing II
Bhaskaran Gopalakrishnan; San Murugesan, Editor(s)

© SPIE. Terms of Use
Back to Top