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

• 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.
• 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.
• 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.
• R. Hassin, and M. Shani, "Machine scheduling with earliness and tardiness and non-execution penalties", Computer & Industrial Engineering, 32 (2005) 683-705.
• G. Li, "Single machine earliness and tardiness scheduling", European Journal of Operational Research, 96 (1997) 546-558.
• 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.
• 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.
• K. R. Baker, G. D. Scudder, "Scheduling with earliness and tardiness penalties: a review", European Journal of Operational Research, 160 (2005) 190-201.
• T. Vallée, and M. Yiltizogli, "Présentation des algorithmes génétiques et leurs applications en économie", Mai 2004, V . 5.
• 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
• 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.
• H. Sun, G. Wang. "Parallel machine earliness and tardiness scheduling with proportional weights". Comput. Oper. Res. , 30 (2003), pp. 801–808.
• 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.
• 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
• Bülbül, K. , Kaminsky, P. , Yano, C. : "Preemption in single machine earliness/tardiness scheduling". Journal of Scheduling 10, 271–292 (2007).
• 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).
• Sourd, F. , Kedad-Sidhoum, S. , "A faster branch-and- bound algorithm for the earliness-tardiness scheduling problem", Journal of Scheduling 11, 49–58 (2008).
• Sourd, F. , "New exact algorithms for one-machine earliness-tardiness scheduling". INFORMS Journal on Computing 21, 167–175 (2009).
• 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).
• 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.
• 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.
• 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.
• 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.