A new multi-objective genetic algorithm for job shop scheduling with limited resources

Mateusz Gorczyca, Alejandra Duenas, Dobrila Petrovic

Research output: Chapter in Book/Report/Conference proceedingConference proceeding

2 Citations (Scopus)

Abstract

The job shop scheduling problem is one of the most frequently analysed problems in classical scheduling theory. Since, generally it is an intractable problem, different ways for solving it are subject of wide interest. This paper presents a new approach to multi-objective job shop scheduling problems based on priority dispatching rules. The objectives considered are to minimise the makespan and to minimise the resource consumption "utilised". The dispatching rules used are some standard dispatching rules related to makespan minimisation. A multi-objeclive genetic algorithm based on a chromosome that is divided into two components is developed. The first component uses the Giffler and Thompson algorithm to determine scheduling coefficients (weights) assigned to each of the dispatching rules for the makespan objective in order to determine the job shop schedule. The second component represents proportions of the resources that are assigned to each operation that need resources. The genetic algorithm's fitness function is defined as the two objectives linearly combined into one objective. The results obtained are encouraging and demonstrate that this approach is useful when the operations performed on different machines require different and limited resources.

Original languageEnglish
Title of host publicationProceedings of the 15th International Conference on Systems Science
EditorsZ. Bubniki, A. Grzech
Pages201-211
Number of pages11
Volume2
Publication statusPublished - 2004
Event15th International Conference on Systems Science - Wroclaw, Poland
Duration: 7 Sep 200410 Sep 2004

Conference

Conference15th International Conference on Systems Science
CountryPoland
CityWroclaw
Period7/09/0410/09/04

Keywords

  • Decision making
  • Dispatching rules
  • Genetic algorithms
  • Job shop scheduling
  • Multi-objective
  • Resource utilisation

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'A new multi-objective genetic algorithm for job shop scheduling with limited resources'. Together they form a unique fingerprint.

Cite this