A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights

A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights

0.00 Avg rating0 Votes
Article ID: iaor19952099
Country: United Kingdom
Volume: 22
Issue: 8
Start Page Number: 857
End Page Number: 869
Publication Date: Oct 1995
Journal: Computers and Operations Research
Authors: ,
Keywords: heuristics
Abstract:

A job scheduling problem with distinct due dates in a single machine is considered. General penalty weights which are not necessarily proportional to the processing times are applied to jobs either early or tardy. An optimal timing algorithm is presented which decides the optimal starting time of each job in a given job sequence. Idle times are inserted between blocks of jobs such that the cost function of each newly created job block is minimized. Prominent near optimal sequences are generated via a genetic algorithm N best reproduction without duplicates, uniform order-based crossover and intra-block mutation operators are employed. The proposed genetic algorithm is proved to outperfrom existing heuristic methods. On average, 12-33% cost reduction effect is obtained by the evolution algorithm compared to the solution by an excellent heuristic procedure. The near optimality of the solutions by the GA is also illustrated by the comparison with an exact algorithm.

Reviews

Required fields are marked *. Your email address will not be published.