Research Article | OPEN ACCESS
An Evolutionary Algorithmic Approach for Single Machine Early Tardy Scheduling Problem
R. Jayabhaduri
Department of Computer Science and Engineering, Sri Venkateswara College of Engineering, Irungattukottai-602 117, Chennai, Tamilnadu, India
Research Journal of Applied Sciences, Engineering and Technology 2015 6:666-673
Received: May 30, 2015 | Accepted: July 8, 2015 | Published: October 25, 2015
Abstract
Most of the real world scheduling problems incorporates Just-In-Time production philosophy which leads to a growing interest in the development of various nature inspired metaheuristic algorithms. Single Machine Early Tardy scheduling problem (SMETP) is one such problem in which jobs have to be scheduled on a single machine against a restrictive common due date parameter and this problem is strongly a NP-hard combinatorial optimization problem. As job sizes vary from 10 to 1000, problems of larger job sizes cannot be solved by exact algorithms. Hence in this research study, we propose genetic algorithm with variations in local search to find an optimal schedule which jointly minimizes the summation of earliness and tardiness cost penalties of 'n' jobs from a common due date by satisfying the three SMETP scheduling properties. The performance of this evolutionary algorithm is validated on the 280 benchmark instances proposed by Biskup and Feldmann for various job sizes and the results show that genetic algorithm works well for smaller job sizes.
Keywords:
Common due date, genetic algorithm, heuristics, local search, single machine scheduling,
Competing interests
The authors have no competing interests.
Open Access Policy
This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Copyright
The authors have no competing interests.
|
|
![](http://www.maxwellsci.com/images/RJASET-maxw.jpg) |
ISSN (Online): 2040-7467
ISSN (Print): 2040-7459 |
![Submit Manuscript](../images/sub.jpg) |
Information |
|
|
|
Sales & Services |
|
|
|