Job-shop scheduling with a combination of evolutionary and heuristic methods

Bela Patkai; Seppo Torvinen

doi:10.1117/12.359504

20 August 1999 Job-shop scheduling with a combination of evolutionary and heuristic methods

Bela Patkai, Seppo Torvinen

Proceedings Volume 3833, Intelligent Systems in Design and Manufacturing II; (1999) https://doi.org/10.1117/12.359504
Event: Photonics East '99, 1999, Boston, MA, United States

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.

Citation Download Citation

Bela Patkai and Seppo Torvinen "Job-shop scheduling with a combination of evolutionary and heuristic methods", Proc. SPIE 3833, Intelligent Systems in Design and Manufacturing II, (20 August 1999); https://doi.org/10.1117/12.359504

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available