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

Fingerprint

Genetic algorithms
Scheduling
Chromosomes
Job shop scheduling

Keywords

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

ASJC Scopus subject areas

  • Engineering(all)

Cite this

Gorczyca, M., Duenas, A., & Petrovic, D. (2004). A new multi-objective genetic algorithm for job shop scheduling with limited resources. In Z. Bubniki, & A. Grzech (Eds.), Proceedings of the 15th International Conference on Systems Science (Vol. 2, pp. 201-211)

A new multi-objective genetic algorithm for job shop scheduling with limited resources. / Gorczyca, Mateusz; Duenas, Alejandra; Petrovic, Dobrila.

Proceedings of the 15th International Conference on Systems Science. ed. / Z. Bubniki; A. Grzech. Vol. 2 2004. p. 201-211.

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

Gorczyca, M, Duenas, A & Petrovic, D 2004, A new multi-objective genetic algorithm for job shop scheduling with limited resources. in Z Bubniki & A Grzech (eds), Proceedings of the 15th International Conference on Systems Science. vol. 2, pp. 201-211, 15th International Conference on Systems Science, Wroclaw, Poland, 7/09/04.
Gorczyca M, Duenas A, Petrovic D. A new multi-objective genetic algorithm for job shop scheduling with limited resources. In Bubniki Z, Grzech A, editors, Proceedings of the 15th International Conference on Systems Science. Vol. 2. 2004. p. 201-211
Gorczyca, Mateusz ; Duenas, Alejandra ; Petrovic, Dobrila. / A new multi-objective genetic algorithm for job shop scheduling with limited resources. Proceedings of the 15th International Conference on Systems Science. editor / Z. Bubniki ; A. Grzech. Vol. 2 2004. pp. 201-211
@inproceedings{0fb869bf27ab45fdb9249c73b8f58b2c,
title = "A new multi-objective genetic algorithm for job shop scheduling with limited resources",
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.",
keywords = "Decision making, Dispatching rules, Genetic algorithms, Job shop scheduling, Multi-objective, Resource utilisation",
author = "Mateusz Gorczyca and Alejandra Duenas and Dobrila Petrovic",
year = "2004",
language = "English",
volume = "2",
pages = "201--211",
editor = "Z. Bubniki and A. Grzech",
booktitle = "Proceedings of the 15th International Conference on Systems Science",

}

TY - GEN

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

AU - Gorczyca, Mateusz

AU - Duenas, Alejandra

AU - Petrovic, Dobrila

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

KW - Decision making

KW - Dispatching rules

KW - Genetic algorithms

KW - Job shop scheduling

KW - Multi-objective

KW - Resource utilisation

UR - http://www.scopus.com/inward/record.url?scp=23844477477&partnerID=8YFLogxK

M3 - Conference proceeding

VL - 2

SP - 201

EP - 211

BT - Proceedings of the 15th International Conference on Systems Science

A2 - Bubniki, Z.

A2 - Grzech, A.

ER -