Fast and meta-heuristics for common due-date assignment and scheduling on parallel machines

Jun Gyu Kim, Ji Su Kim, Dong-Ho Lee

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

This study considers common due-date assignment and scheduling on parallel machines. The problem has three decision variables: assigning the common-due-date, allocating jobs to parallel machines, and sequencing the jobs assigned to each machine. The objective is to minimise the sum of due-date assignment, earliness and tardiness penalties. A mathematical programming model is presented, and then two types of heuristics are suggested after characterising the optimal solution properties. The two types of heuristics are: (a) a fast two-stage heuristic with obtaining an initial solution and improvement; and (b) two meta-heuristics, tabu search and simulated annealing, with new neighbourhood generation methods. Computational experiments were conducted on a number of test instances, and the results show that each of the heuristic types outperforms the existing one. In particular, the meta-heuristics suggested in this study are significantly better than the existing genetic algorithm.

Original languageEnglish
Pages (from-to)6040-6057
Number of pages18
JournalInternational Journal of Production Research
Volume50
Issue number20
DOIs
StatePublished - 2012 Oct 15

Fingerprint

Tabu search
Mathematical programming
Simulated annealing
Genetic algorithms
Scheduling
Experiments
Metaheuristics
Heuristics
Due date assignment
Parallel machines

Keywords

  • common due-date assignment
  • fast heuristics
  • meta-heuristics
  • parallel machine scheduling

Cite this

@article{5a78fe4116c847f3a4613e212edcb6e3,
title = "Fast and meta-heuristics for common due-date assignment and scheduling on parallel machines",
abstract = "This study considers common due-date assignment and scheduling on parallel machines. The problem has three decision variables: assigning the common-due-date, allocating jobs to parallel machines, and sequencing the jobs assigned to each machine. The objective is to minimise the sum of due-date assignment, earliness and tardiness penalties. A mathematical programming model is presented, and then two types of heuristics are suggested after characterising the optimal solution properties. The two types of heuristics are: (a) a fast two-stage heuristic with obtaining an initial solution and improvement; and (b) two meta-heuristics, tabu search and simulated annealing, with new neighbourhood generation methods. Computational experiments were conducted on a number of test instances, and the results show that each of the heuristic types outperforms the existing one. In particular, the meta-heuristics suggested in this study are significantly better than the existing genetic algorithm.",
keywords = "common due-date assignment, fast heuristics, meta-heuristics, parallel machine scheduling",
author = "Kim, {Jun Gyu} and Kim, {Ji Su} and Dong-Ho Lee",
year = "2012",
month = "10",
day = "15",
doi = "10.1080/00207543.2011.644591",
language = "English",
volume = "50",
pages = "6040--6057",
journal = "International Journal of Production Research",
issn = "0020-7543",
number = "20",

}

Fast and meta-heuristics for common due-date assignment and scheduling on parallel machines. / Kim, Jun Gyu; Kim, Ji Su; Lee, Dong-Ho.

In: International Journal of Production Research, Vol. 50, No. 20, 15.10.2012, p. 6040-6057.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Fast and meta-heuristics for common due-date assignment and scheduling on parallel machines

AU - Kim, Jun Gyu

AU - Kim, Ji Su

AU - Lee, Dong-Ho

PY - 2012/10/15

Y1 - 2012/10/15

N2 - This study considers common due-date assignment and scheduling on parallel machines. The problem has three decision variables: assigning the common-due-date, allocating jobs to parallel machines, and sequencing the jobs assigned to each machine. The objective is to minimise the sum of due-date assignment, earliness and tardiness penalties. A mathematical programming model is presented, and then two types of heuristics are suggested after characterising the optimal solution properties. The two types of heuristics are: (a) a fast two-stage heuristic with obtaining an initial solution and improvement; and (b) two meta-heuristics, tabu search and simulated annealing, with new neighbourhood generation methods. Computational experiments were conducted on a number of test instances, and the results show that each of the heuristic types outperforms the existing one. In particular, the meta-heuristics suggested in this study are significantly better than the existing genetic algorithm.

AB - This study considers common due-date assignment and scheduling on parallel machines. The problem has three decision variables: assigning the common-due-date, allocating jobs to parallel machines, and sequencing the jobs assigned to each machine. The objective is to minimise the sum of due-date assignment, earliness and tardiness penalties. A mathematical programming model is presented, and then two types of heuristics are suggested after characterising the optimal solution properties. The two types of heuristics are: (a) a fast two-stage heuristic with obtaining an initial solution and improvement; and (b) two meta-heuristics, tabu search and simulated annealing, with new neighbourhood generation methods. Computational experiments were conducted on a number of test instances, and the results show that each of the heuristic types outperforms the existing one. In particular, the meta-heuristics suggested in this study are significantly better than the existing genetic algorithm.

KW - common due-date assignment

KW - fast heuristics

KW - meta-heuristics

KW - parallel machine scheduling

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

U2 - 10.1080/00207543.2011.644591

DO - 10.1080/00207543.2011.644591

M3 - Article

AN - SCOPUS:84867357333

VL - 50

SP - 6040

EP - 6057

JO - International Journal of Production Research

JF - International Journal of Production Research

SN - 0020-7543

IS - 20

ER -