A Genetic Algorithm for Scheduling n Jobs on a Single Machine with a Stochastic Controllable Processing, Tooling Cost and Earliness-Tardiness Penalties
- 1 Zagazig University, Egypt
Abstract
Problem statement: In this research, we addressed the problem of minimizing the earliness-tardiness penalties and manufacturing costs of a single machine with a stochastic controllable processing and tooling cost. Approach: We developed a mathematical non-linear integer programming model and its linearised version to find the optimal solution. We introduced a new genome representation in single machine scheduling literature that evolved by a genetic algorithm to solve the problem. The genome representation includes two genes per job, one represents the job starting time and other corresponds to the job processing time. The algorithms were compared based on the solution quality, CPU time and memory consumption in bytes on a set of randomly generated test problems. Results: The results showed that developed algorithms could define the global optimal solution of most scheduling problems with n ≤ 20 jobs. For larger n, the developed genetic algorithm outperforms the math models in terms of solution quality and less CPU seconds while consumes moderate memory kilobytes of 3295 compared with 5058 and 1685 of linear and nonlinear models on the average. Conclusion: The GA's average performance achieves 6.013 related to the lower bound of math linear program whereas nonlinear model achieves an average of 1.034. The GA's performance increases by increasing n compared with other techniques. We hope to expand the developed algorithms for different configurations as parallel and job shops.
DOI: https://doi.org/10.3844/ajeassp.2011.341.349
Copyright: © 2011 Mohamed Ali Abdel-Fattah Mansour. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
- 4,149 Views
- 3,192 Downloads
- 0 Citations
Download
Keywords
- Single machine scheduling
- controllable processing times
- earliness-tardiness
- mathematical programming
- mixed integer
- Non-Linear Integer Math Programming (NLIP)
- Tightness Factor (TF)
- Genetic Algorithm (GA)
- linearised model
- CPU seconds