Early-tardy scheduling under fuzzy due dates using a genetic algorithm

S. S. Lam, X. Cai

Research output: Contribution to conferencePaperpeer-review

Abstract

We consider the problem of scheduling n jobs on a single machine. Each job i has a processing time p/sub i/, a weight w/sub i/, and a due date D/sub i/, which is a fuzzy number with a triangular membership function. The problem is to determine: (i) a job sequence, and (ii) a set of idle times each before one job, so as to minimize the total weighted earliness and tardiness cost under the fuzzy due dates. We first introduce a fuzzy distance function to measure the deviation of the completion time of a job from its fuzzy due date. We show that, given a job sequence, the problem of determining the optimal idle times is a continuous and convex optimization problem with a differentiable objective function, although the objective function after applying the fuzzy distance measure becomes nonlinear. We devise a genetic algorithm (GA) to tackle the problem, using a pigeon-hole coding scheme to represent a sequence and a nonlinear optimizer to determine the idle times. We evaluate the solutions obtained by such a GA as compared to the solutions obtained by treating the due dates as crispy numbers equal to the mean values of its fuzzy partners.

Original languageEnglish
Pages1079-1084
Number of pages6
DOIs
Publication statusPublished - 1999
Event1999 Congress on Evolutionary Computation, CEC 1999 - Washington, DC, United States
Duration: 6 Jul 19999 Jul 1999

Conference

Conference1999 Congress on Evolutionary Computation, CEC 1999
Country/TerritoryUnited States
CityWashington, DC
Period6/07/999/07/99

Fingerprint

Dive into the research topics of 'Early-tardy scheduling under fuzzy due dates using a genetic algorithm'. Together they form a unique fingerprint.

Cite this