Using a family of critical ratio-based approaches to minimize the number of tardy jobs in the job shop with sequence dependent setup times

Tsung-Che Chiang, Li Chen Fu

Research output: Contribution to journalArticle

25 Citations (Scopus)

Abstract

This paper addresses the job shop scheduling problem to minimize the number of tardy jobs, considering the sequence dependent setup time. This problem is taken as a sequencing problem, and a family of approaches with different levels of intricacy is proposed. The simplest form is a critical ratio-based dispatching rule, which leads to satisfactory solutions by taking into account the group information rather than only the individual information of jobs. Then, an enhanced approach consisting of an iterative schedule refining mechanism will be given. Its feature is to iteratively adjust the estimation of the remaining processing times of jobs in a dynamic and operation-specific manner. Finally, a genetic algorithm which takes the dispatching rule and the refining mechanism as the core is proposed. The performance of these approaches is carefully examined by a comprehensive experimental study.

Original languageEnglish
Pages (from-to)78-92
Number of pages15
JournalEuropean Journal of Operational Research
Volume196
Issue number1
DOIs
Publication statusPublished - 2009 Jul 1

Fingerprint

Sequence-dependent Setup Times
Dispatching Rules
Job Shop
Refining
Minimise
Job Shop Scheduling Problem
Sequencing
Experimental Study
Schedule
Genetic algorithms
Genetic Algorithm
Processing
Family
Job shop
Sequence-dependent setup times
Dispatching rules
Form
Job shop scheduling

Keywords

  • Dispatching rules
  • Genetic algorithms
  • Job shop
  • Scheduling
  • Sequence dependent setup

ASJC Scopus subject areas

  • Information Systems and Management
  • Management Science and Operations Research
  • Modelling and Simulation

Cite this

@article{3748594e45fb42bd80d2df8013229366,
title = "Using a family of critical ratio-based approaches to minimize the number of tardy jobs in the job shop with sequence dependent setup times",
abstract = "This paper addresses the job shop scheduling problem to minimize the number of tardy jobs, considering the sequence dependent setup time. This problem is taken as a sequencing problem, and a family of approaches with different levels of intricacy is proposed. The simplest form is a critical ratio-based dispatching rule, which leads to satisfactory solutions by taking into account the group information rather than only the individual information of jobs. Then, an enhanced approach consisting of an iterative schedule refining mechanism will be given. Its feature is to iteratively adjust the estimation of the remaining processing times of jobs in a dynamic and operation-specific manner. Finally, a genetic algorithm which takes the dispatching rule and the refining mechanism as the core is proposed. The performance of these approaches is carefully examined by a comprehensive experimental study.",
keywords = "Dispatching rules, Genetic algorithms, Job shop, Scheduling, Sequence dependent setup",
author = "Tsung-Che Chiang and Fu, {Li Chen}",
year = "2009",
month = "7",
day = "1",
doi = "10.1016/j.ejor.2007.12.042",
language = "English",
volume = "196",
pages = "78--92",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "1",

}

TY - JOUR

T1 - Using a family of critical ratio-based approaches to minimize the number of tardy jobs in the job shop with sequence dependent setup times

AU - Chiang, Tsung-Che

AU - Fu, Li Chen

PY - 2009/7/1

Y1 - 2009/7/1

N2 - This paper addresses the job shop scheduling problem to minimize the number of tardy jobs, considering the sequence dependent setup time. This problem is taken as a sequencing problem, and a family of approaches with different levels of intricacy is proposed. The simplest form is a critical ratio-based dispatching rule, which leads to satisfactory solutions by taking into account the group information rather than only the individual information of jobs. Then, an enhanced approach consisting of an iterative schedule refining mechanism will be given. Its feature is to iteratively adjust the estimation of the remaining processing times of jobs in a dynamic and operation-specific manner. Finally, a genetic algorithm which takes the dispatching rule and the refining mechanism as the core is proposed. The performance of these approaches is carefully examined by a comprehensive experimental study.

AB - This paper addresses the job shop scheduling problem to minimize the number of tardy jobs, considering the sequence dependent setup time. This problem is taken as a sequencing problem, and a family of approaches with different levels of intricacy is proposed. The simplest form is a critical ratio-based dispatching rule, which leads to satisfactory solutions by taking into account the group information rather than only the individual information of jobs. Then, an enhanced approach consisting of an iterative schedule refining mechanism will be given. Its feature is to iteratively adjust the estimation of the remaining processing times of jobs in a dynamic and operation-specific manner. Finally, a genetic algorithm which takes the dispatching rule and the refining mechanism as the core is proposed. The performance of these approaches is carefully examined by a comprehensive experimental study.

KW - Dispatching rules

KW - Genetic algorithms

KW - Job shop

KW - Scheduling

KW - Sequence dependent setup

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

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

U2 - 10.1016/j.ejor.2007.12.042

DO - 10.1016/j.ejor.2007.12.042

M3 - Article

AN - SCOPUS:56549104206

VL - 196

SP - 78

EP - 92

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -