CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Hybrid Algorithm for Optimization Problems Applied to Single Machine Scheduling

by Hemmak Allaoua, Bouderah Brahim
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 66 - Number 24
Year of Publication: 2013
Authors: Hemmak Allaoua, Bouderah Brahim
10.5120/11262-5749

Hemmak Allaoua, Bouderah Brahim . Hybrid Algorithm for Optimization Problems Applied to Single Machine Scheduling. International Journal of Computer Applications. 66, 24 ( March 2013), 7-11. DOI=10.5120/11262-5749

@article{ 10.5120/11262-5749,
author = { Hemmak Allaoua, Bouderah Brahim },
title = { Hybrid Algorithm for Optimization Problems Applied to Single Machine Scheduling },
journal = { International Journal of Computer Applications },
issue_date = { March 2013 },
volume = { 66 },
number = { 24 },
month = { March },
year = { 2013 },
issn = { 0975-8887 },
pages = { 7-11 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume66/number24/11262-5749/ },
doi = { 10.5120/11262-5749 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:23:17.115533+05:30
%A Hemmak Allaoua
%A Bouderah Brahim
%T Hybrid Algorithm for Optimization Problems Applied to Single Machine Scheduling
%J International Journal of Computer Applications
%@ 0975-8887
%V 66
%N 24
%P 7-11
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In this paper, we will present a new variant of genetic algorithm to solve optimization problems where the number of feasible solutions is very important. This approach consists on a hybrid algorithm between genetic algorithms introduced by J. Holland (1975) and dynamic programming method of R. Bellman (1957). Then we will apply this hybrid algorithm to solve a single machine scheduling problem that consists to minimizing the sum of earliness and tardiness costs with common due date. Our goal is designing a new approach to find a good near solutions for combinatory problems as scheduling problems or traveling salesman problem which have an exponential number of solutions and known as NP-hard problems.

References
  1. M. Feldman, and D. Biskup, "Single-machine scheduling for minimizing earliness and tardiness penalties by meat-heuristic approaches", Computer & Industrial Engineering, 44 (2003) 307-323.
  2. M. Feldman, and D. Biskup, "Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates", Computer & Industrial Engineering, 28 (2001) 787-801.
  3. M. Feldman, and D. Biskup, "Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates", Computer & Industrial Engineering, 28 (2001) 787-801.
  4. R. Hassin, and M. Shani, "Machine scheduling with earliness and tardiness and non-execution penalties", Computer & Industrial Engineering, 32 (2005) 683-705.
  5. G. Li, "Single machine earliness and tardiness scheduling", European Journal of Operational Research, 96 (1997) 546-558.
  6. S. W. Lin, S. Y. Chou and K. C. Ying, "A sequential exchange approach for minimizing earliness-tardiness penalties of single machine scheduling with a common due date", European Journal of Operational Research, xx Volume 177, Issue 2, Pages 1294–1301.
  7. C. M. Hino, D. P. Ronconi, A. B. Mendes, "Minimizing earliness and tardiness penalties in a single machine problem with a common due date ", European Journal of Operational Research, 160 (2005) 190-201.
  8. K. R. Baker, G. D. Scudder, "Scheduling with earliness and tardiness penalties: a review", European Journal of Operational Research, 160 (2005) 190-201.
  9. T. Vallée, and M. Yiltizogli, "Présentation des algorithmes génétiques et leurs applications en économie", Mai 2004, V . 5.
  10. C. S. Sung, J. I. Min. "Scheduling in a two-machine flow shop with batch processing machine(s) for earliness/tardiness measure under a common due date". European J. Oper. Res. , 131 (2001), pp. 95–106
  11. J. Bank, F. Werner. "Heuristic algorithms for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties". Mathl. Comput. Modelling, 33 (4/5) (2001), pp. 363–383.
  12. H. Sun, G. Wang. "Parallel machine earliness and tardiness scheduling with proportional weights". Comput. Oper. Res. , 30 (2003), pp. 801–808.
  13. Ching-Jong Liao, Che-Ching Cheng. "A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date". Computers & Industrial Engineering. Volume 52, Issue 4, May 2007, Pages 404–413.
  14. Liu Min, Wu Cheng. "Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems". Robotics and Computer-Integrated Manufacturing. Volume 22, Issue 4, August 2006, Pages 279–287
  15. Bülbül, K. , Kaminsky, P. , Yano, C. : "Preemption in single machine earliness/tardiness scheduling". Journal of Scheduling 10, 271–292 (2007).
  16. Detienne, B. , Pinson, E. , Rivreau. , D. : "Lagrangian domain reductions for the single machine earliness-tardiness problem with release dates", European Journal of Operational Research 201, 45–54 (2010).
  17. Sourd, F. , Kedad-Sidhoum, S. , "A faster branch-and- bound algorithm for the earliness-tardiness scheduling problem", Journal of Scheduling 11, 49–58 (2008).
  18. Sourd, F. , "New exact algorithms for one-machine earliness-tardiness scheduling". INFORMS Journal on Computing 21, 167–175 (2009).
  19. Yau, H. , Pan, Y. , Shi, L. , "New solution approaches to the general single machine earliness tardiness problem". IEEE Transactions on Automation Science and Engineering 5, 349–360 (2008).
  20. Débora P. Ronconi; Márcio S. Kawamura , "The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm", Comput. Appl. Math. vol. 29 no. 2 São Carlos June 2010.
  21. S. Webster, D. Jog & A. Gupta, "A genetic algorithm for scheduling job families on a single machine with arbitrary earliness/tardiness penalties and an unrestricted common due date", International Journal of Production Research. Volume 36, Issue 9, pp. 2543-2551, 1998.
  22. Shih-Hsin Chen, Min-Chih Chen, Pei-Chann Chang, and Yuh-Min Chen, "EA/G-GA for Single Machine Scheduling Problems with Earliness/Tardiness Costs", Entropy 2011, 13, 1152-1169; doi:10. 3390/e13061152.
  23. Chang, P. C. ; Chen, S. H. ; Liu, C. H. "Sub-population genetic algorithm with mining gene structures for multiobjective flowshop scheduling problems". Expert Syst. Appl. 2007, 33, 762–771.
Index Terms

Computer Science
Information Sciences

Keywords

Genetic Algorithm Scheduling Dynamic programming Optimization

Powered by PhDFocusTM