Rachel Hunt
ABSTRACT
Job Shop Scheduling (JSS) is a complex real-world problem aiming to optimise a measure of delivery speed or customer satisfaction by determining a schedule for processing jobs on machines. A major disadvantage of using a dispatching rule (DR) approach to solving JSS problems is their lack of a global perspective of the current and potential future state of the shop. We investigate a genetic programming based hyper-heuristic (GPHH) approach to develop "less-myopic" DRs for dynamic JSS. Results show that in the dynamic ten machine job shop, incorporating features of the state of the wider shop, and the stage of a job's journey through the shop, improves the mean performance, and decreases the standard deviation of performance of the best evolved rules.
- H. Aytug, M. A. Lawley, K. McKay, S. Mohan, and R. Uzsoy. Executing production schedules in the face of uncertainties: A review and some future directions. European Journal of Operational Research, 161(1):86--110, 2005.Google Scholar
Cross Ref
- K. Bhaskaran and M. Pinedo. Dispatching. Handbook of Industrial Engineering, pages 2184--2198, 1992.Google Scholar
- J. Blazewicz, W. Domschke, and E. Pesch. The job shop scheduling problem: Conventional and new solution techniques. European Journal of Operational Research, 93(1):1--33, 1996.Google ScholarCross Ref
- J. Branke and C. Pickardt. Evolutionary search for difficult problem instances to support the design of job shop dispatching rules. European Journal of Operational Research, 212(1):22--32, 2011.Google ScholarCross Ref
- E. Burke, M. Hyde, G. Kendall, G. Ochoa, E. Ozcan, and J. R. Woodward. A classification of hyper-heuristic approaches. In M. Gendreau and J.-Y. Potvin, editors, Handbook of Meta-Heuristics, pages 449--468. Kluwer, 2010.Google Scholar
- E. K. Burke, M. R. Hyde, G. Kendall, G. Ochoa, E. Ozcan, and J. R. Woodward. Exploring hyper-heuristic methodologies with genetic programming. In C. Mumford and L. Jain, editors, Computational Intelligence, volume 1 of Intelligent Systems Reference Library, pages 177--201. Springer, 2009.Google Scholar
- C. Geiger, R. Uzsoy, and H. Aytug. Rapid modeling and discovery of priority dispatching rules: an autonomous learning approach. Journal of Scheduling, 9(1):7--34, 2006. Google ScholarDigital Library
- W. S. Gere, Jr. Heuristics in job shop scheduling. Management Science, 13(3):167--190, 1966.Google ScholarDigital Library
- E. Hart, P. Ross, and D. Corne. Evolutionary scheduling: a review. Genetic Programming and Evolvable Machines, 6:191--220, 2005. Google ScholarDigital Library
- T. Hildebrandt, J. Heger, and B. Scholz-Reiter. Towards improved dispatching rules for complex shop floor scenarios: a genetic programming approach. In GECCO '10: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, pages 257--264, 2010. Google ScholarDigital Library
- D. Jakobovic, L. Jelenkovic, and L. Budin. Genetic programming heuristics for multiple machine scheduling. In EuroGP'07: Proceedings of the 10th European Conference on Genetic programming, pages 321--330, 2007. Google ScholarDigital Library
- D. Jakobović and K. Marasović. Evolving priority scheduling heuristics with genetic programming. Applied Soft Computing, 12(9):2781--2789, 2012. Google ScholarDigital Library
- A. Jones and L. C. Rabelo. Survey of job shop scheduling techniques. Technical report, National Institute of Standards and Technology, Gaithersberg, 1998.Google Scholar
- J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992. Google ScholarDigital Library
- S. Luke. Essentials of Metaheuristics. Lulu, second edition, 2013. Available for free at http://cs.gmu.edu/$\sim$sean/book/metaheuristics/.Google Scholar
- R. I. McKay, N. X. Hoai, P. A. Whigham, Y. Shan, and M. O\rqNeill. Grammar-based genetic programming: a survey. Genetic Programming and Evolvable Machines, 11(3--4):365--396, 2010. Google ScholarDigital Library
- K. Miyashita. Job-shop scheduling with GP. In GECCO'00: Proceedings of the Genetic and Evolutionary Computation Conference, pages 505--512, 2000.Google Scholar
- S. Nguyen, M. Zhang, M. Johnston, and K. Tan. Learning iterative dispatching rules for job shop scheduling with genetic programming. The International Journal of Advanced Manufacturing Technology, 67(1--4):85--100, 2013.Google ScholarCross Ref
- S. Nguyen, M. Zhang, M. Johnston, and K. C. Tan. A coevolution genetic programming method to evolve scheduling policies for dynamic multi-objective job shop scheduling problems. In Proceedings of the 2012 IEEE Congress on Evolutionary Computation, pages 1--8, 2012.Google ScholarCross Ref
- S. Nguyen, M. Zhang, M. Johnston, and K. C. Tan. A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem. IEEE Transactions on Evolutionary Computation, 17(5):621--639, 2013.Google ScholarDigital Library
- Nguyen Su, Zhang Mengjie, Johnston Mark, and Tan Kay Chen. Genetic programming for evolving due-date assignment models in job shop environments. Evolutionary Computation, 22(1):105--138, 2013. Google ScholarDigital Library
- C. W. Pickardt, T. Hildebrandt, J. Branke, J. Heger, and B. Scholz-Reiter. Evolutionary generation of dispatching rule sets for complex dynamic scheduling problems. International Journal of Production Economics, 145(1):67--77, 2013.Google ScholarCross Ref
- M. L. Pinedo. Scheduling: Theory, Algorithms, and Systems. 3rd edition, Springer, 2008. Google ScholarDigital Library
- C. Potts and V. Strusevich. Fifty years of scheduling: a survey of milestones. Journal of the Operational Research Society, 60(S1):41--68, 2009.Google ScholarCross Ref
- J. C. Tay and N. B. Ho. Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems. Computer & Industrial Engineering, 54:453--473, 2008. Google ScholarDigital Library
- A. Vepsalainen and T. Morton. Priority rules for job shops with weighted tardiness costs. Management Science, 33:1035--1047, 1987. Google ScholarDigital Library
Index Terms
- Evolving "less-myopic" scheduling rules for dynamic job shop scheduling with genetic programming
Recommendations
Genetic programming for evolving due-date assignment models in job shop environments
Due-date assignment plays an important role in scheduling systems and strongly influences the delivery performance of job shops. Because of the stochastic and dynamic nature of job shops, the development of general due-date assignment models DDAMs is ...
Evolving reusable operation-based due-date assignment models for job shop scheduling with genetic programming
EuroGP'12: Proceedings of the 15th European conference on Genetic ProgrammingDue-date assignment plays an important role in scheduling systems and strongly influences the delivery performance of job shops. Because of the stochastic and dynamic features of job shops, the development of general due-date assignment models (DDAMs) ...
Flow shop scheduling with two distinct job due dates
Highlights- Flow shop scheduling problems with two distinct job due dates.
- Solvability with ...
AbstractWe consider flow shop scheduling problems with two distinct job due dates. Motivated by the NP-hardness of these problems with arbitrary job processing times, we focus on their solvability with ordered or proportionate job processing ...
Comments