An iterated greedy algorithm for total flow time minimization in unrelated parallel batch machines with unequal job release times

José Elias C. Arroyo, Joseph Leung, Ricardo Gonçalves Tavares

Research output: Contribution to journalArticle

Abstract

This paper investigates the problem of scheduling a set of jobs with arbitrary sizes and non-zero release times on a set of unrelated parallel batch machines with different capacities so as to minimize the total flow time of the jobs. The total flow time, defined as the total amount of time that the jobs spend in the system (i.e. the period between the job release dates and its completion times), is one of the most important objectives in scheduling problems, since it can lead to stable utilization of resources and reduction of working-in-process inventory. Motivated by the computational complexity of the problem, a simple and effective iterated greedy (IG) algorithm is proposed to solve it. The IG algorithm uses an efficient greedy heuristic to reconstruct solutions and a local search procedure to further enhance the solution quality. In attempting to obtain optimal solutions for small-medium size instances, a mixed integer programming model for the problem is also presented. The performance of the proposed algorithm is tested on a comprehensive set of small, medium and large benchmark of randomly generated instances, and is compared to three benchmark meta-heuristic algorithms (Discrete Differential Evolution, Ant Colony Optimization and Simulated Annealing) recently proposed for similar parallel batch machine scheduling problems. Experimental results and statistical tests show that the proposed algorithm is significantly superior in performance than the other algorithms.

LanguageEnglish (US)
Pages239-254
Number of pages16
JournalEngineering Applications of Artificial Intelligence
Volume77
DOIs
StatePublished - Jan 1 2019

Fingerprint

Scheduling
Statistical tests
Ant colony optimization
Integer programming
Heuristic algorithms
Simulated annealing
Computational complexity

Cite this

@article{bea2824f7dfc42c49228faae0e757d5d,
title = "An iterated greedy algorithm for total flow time minimization in unrelated parallel batch machines with unequal job release times",
abstract = "This paper investigates the problem of scheduling a set of jobs with arbitrary sizes and non-zero release times on a set of unrelated parallel batch machines with different capacities so as to minimize the total flow time of the jobs. The total flow time, defined as the total amount of time that the jobs spend in the system (i.e. the period between the job release dates and its completion times), is one of the most important objectives in scheduling problems, since it can lead to stable utilization of resources and reduction of working-in-process inventory. Motivated by the computational complexity of the problem, a simple and effective iterated greedy (IG) algorithm is proposed to solve it. The IG algorithm uses an efficient greedy heuristic to reconstruct solutions and a local search procedure to further enhance the solution quality. In attempting to obtain optimal solutions for small-medium size instances, a mixed integer programming model for the problem is also presented. The performance of the proposed algorithm is tested on a comprehensive set of small, medium and large benchmark of randomly generated instances, and is compared to three benchmark meta-heuristic algorithms (Discrete Differential Evolution, Ant Colony Optimization and Simulated Annealing) recently proposed for similar parallel batch machine scheduling problems. Experimental results and statistical tests show that the proposed algorithm is significantly superior in performance than the other algorithms.",
author = "Arroyo, {Jos{\'e} Elias C.} and Joseph Leung and Tavares, {Ricardo Gon{\cc}alves}",
year = "2019",
month = "1",
day = "1",
doi = "https://doi.org/10.1016/j.engappai.2018.10.012",
language = "English (US)",
volume = "77",
pages = "239--254",
journal = "Engineering Applications of Artificial Intelligence",
issn = "0952-1976",
publisher = "Elsevier Limited",

}

An iterated greedy algorithm for total flow time minimization in unrelated parallel batch machines with unequal job release times. / Arroyo, José Elias C.; Leung, Joseph; Tavares, Ricardo Gonçalves.

In: Engineering Applications of Artificial Intelligence, Vol. 77, 01.01.2019, p. 239-254.

Research output: Contribution to journalArticle

TY - JOUR

T1 - An iterated greedy algorithm for total flow time minimization in unrelated parallel batch machines with unequal job release times

AU - Arroyo, José Elias C.

AU - Leung, Joseph

AU - Tavares, Ricardo Gonçalves

PY - 2019/1/1

Y1 - 2019/1/1

N2 - This paper investigates the problem of scheduling a set of jobs with arbitrary sizes and non-zero release times on a set of unrelated parallel batch machines with different capacities so as to minimize the total flow time of the jobs. The total flow time, defined as the total amount of time that the jobs spend in the system (i.e. the period between the job release dates and its completion times), is one of the most important objectives in scheduling problems, since it can lead to stable utilization of resources and reduction of working-in-process inventory. Motivated by the computational complexity of the problem, a simple and effective iterated greedy (IG) algorithm is proposed to solve it. The IG algorithm uses an efficient greedy heuristic to reconstruct solutions and a local search procedure to further enhance the solution quality. In attempting to obtain optimal solutions for small-medium size instances, a mixed integer programming model for the problem is also presented. The performance of the proposed algorithm is tested on a comprehensive set of small, medium and large benchmark of randomly generated instances, and is compared to three benchmark meta-heuristic algorithms (Discrete Differential Evolution, Ant Colony Optimization and Simulated Annealing) recently proposed for similar parallel batch machine scheduling problems. Experimental results and statistical tests show that the proposed algorithm is significantly superior in performance than the other algorithms.

AB - This paper investigates the problem of scheduling a set of jobs with arbitrary sizes and non-zero release times on a set of unrelated parallel batch machines with different capacities so as to minimize the total flow time of the jobs. The total flow time, defined as the total amount of time that the jobs spend in the system (i.e. the period between the job release dates and its completion times), is one of the most important objectives in scheduling problems, since it can lead to stable utilization of resources and reduction of working-in-process inventory. Motivated by the computational complexity of the problem, a simple and effective iterated greedy (IG) algorithm is proposed to solve it. The IG algorithm uses an efficient greedy heuristic to reconstruct solutions and a local search procedure to further enhance the solution quality. In attempting to obtain optimal solutions for small-medium size instances, a mixed integer programming model for the problem is also presented. The performance of the proposed algorithm is tested on a comprehensive set of small, medium and large benchmark of randomly generated instances, and is compared to three benchmark meta-heuristic algorithms (Discrete Differential Evolution, Ant Colony Optimization and Simulated Annealing) recently proposed for similar parallel batch machine scheduling problems. Experimental results and statistical tests show that the proposed algorithm is significantly superior in performance than the other algorithms.

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

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

U2 - https://doi.org/10.1016/j.engappai.2018.10.012

DO - https://doi.org/10.1016/j.engappai.2018.10.012

M3 - Article

VL - 77

SP - 239

EP - 254

JO - Engineering Applications of Artificial Intelligence

T2 - Engineering Applications of Artificial Intelligence

JF - Engineering Applications of Artificial Intelligence

SN - 0952-1976

ER -