Abstract
Flexible job shop scheduling problem (FJSSP) is generalization of job shop scheduling problem (JSSP), in which an operation may be processed on more than one machine each of which has the same function. Most previous researches on FJSSP assumed that all jobs to be processed are available at the beginning of scheduling horizon. The assumption, however, is always violated in practical industries because jobs usually arrive over time and can not be predicted before their arrivals. In the paper, dynamic flexible job shop scheduling problem (DFJSSP) with job release dates is studied. A heuristic is proposed to implement reactive scheduling for the dynamic scheduling problem. An approach based on gene expression programming (GEP) is also proposed which automatically constructs reactive scheduling policies for the dynamic scheduling. In order to evaluate the performance of the reactive scheduling policies constructed by the proposed GEP-based approach under a variety of processing conditions three factors, such as the shop utilization, due date tightness, problem flexibility, are considered in the simulation experiments. The scheduling performance measure considered in the simulation is the minimization of makespan, mean flowtime and mean tardiness, respectively. The results show that GEP-based approach can construct more efficient reactive scheduling policies for DFJSSP with job release dates under a big range of processing conditions and performance measures in the comparison with previous approaches.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aissani, N., Bekrar, A., Trentesaux, D., & Beldjitali, B. (2011). Dynamic scheduling for multi-site companies: A decisional approach based on reinforcement multi-agent learning. Journal of Intelligent Manufacturing, Online.
Arnaout J. P., Rabadi G., Musa R. (2010) A two-stage Ant Colony Optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times. Journal of Intelligent Manufacturing 21(6): 693–701
Atlan, L., Bonnet, J., & Naillon, M. (1994). Learning distributed reactive strategies by genetic programming for the general job shop problem. In D., Dankel & Stewan J. (Eds.), Proceedings of The 7th annual Florida artificial intelligence research symposium Pensacola : IEEE Press. 5–6 May 1994.
Aytug H., Lawley M. A., McKay K., Mohan S., Uzsoy R. (2005) Executing production schedules in the face of uncertainties: A review and some future directions. European Journal of Operational Research 161(1): 86–110
Baker K. R. (1974) Introduction to sequencing and scheduling. Wiley, New York
Blackstone J. H., Phillips D. T., Hogg G. L. (1982) A state-of the-art survey of dispatching rules for manufacturing job shop operations. International Journal of Production Research 20(1): 27–45
Dimopoulos C., Zalzala A. M. S. (2001) Investigating the use of genetic programming for a classic one-machine scheduling problem. Advances in Engineering Software 32(6): 489–498
Ferreira C. (2001) Gene expression programming: A new adaptive algorithm for solving problems. Complex System 13(2): 87–129
Garey M. R., Johnson D. S., Sethi R. (1976) The complexity of flow shop and job shop scheduling. Mathematics of Operations Research 1(2): 117–129
Geiger C. D., Uzsoy R., Aytug H. (2006) Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach. Journal of Scheduling 9(1): 7–34
Goldberg D. E. (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Boston
Hardy Y., Steeb W. H. (2002) Gene expression programming and one-dimensional chaotic maps. Internal Journal of Modern Physics C 13(1): 13–24
Ho, N. B., & Tay, J. C. (2004). GENACE: An efficient cultural algorithm for solving the flexbile job-shop problem. In Proceedings of the congress on evolutionary computation CEC2004 (pp. 1759–1766).
Ho N. B., Tay J. C., Lai E. M. K. (2007) An effective architecture for learning and evolving flexible job-shop schedules. European Journal of Operational Research 179(2): 316–333
Holthaus O., Rajendran C. (1997) Efficient dispatching rules for scheduling in a job shop. Internal Journal of Production Economics 48(1): 87–105
Jain A. S., Meeran S. (1998) Deterministic job-shop scheduling: Past, present and future. European Journal of Operational Research 113(2): 390–434
Jakobovic D., Budin L. (2006) Dynamic scheduling with genetic programming. Lecture Notes of Computer Science 3905: 73–84
Jensen M. T. (2003) Generating robust and flexible job shop schedules using genetic algorithms. IEEE Transactions on Evolutionary Computation 7(3): 275–288
Koza, J. R. (2007). Introduction to genetic programming. In: H. Lipson (Eds.), Proceedings of GECCO 2007: Genetic and evolutionary computation conference (pp. 3323–3365). London: ACM Press. 7–11 July 2007.
Li, L., & Wang, K. Q. (2009). Multi-objective flexible job shop schedule based on improved Ant Colony Algorithm. In Proceedings of ICIA2009: International conference on information and automation (pp. 1158–1162). 1–3.
Mavrikios, D., Papakostas, N., Mourtzis, D., & Chryssolouris, G. (2011). On industrial learning and training for the factories of the future: a conceptual, cognitive and technology framework. Journal of Intelligent Manufacturing Online.
Miyashita, K. (2000). Job-shop scheduling with genetic programming. In L. D. Whitley & D. E. Goldberg et al. (Eds.), Proceedings of genetic and evolutionary computation conference (GECCO-2000) (pp. 505–512). Las Vegas: Morgan Kaufmann. 8–12 July 2000.
Panwalkar S., Wafik I. (1977) A survey of scheduling rules. Operations Research 25(1): 45–61
Pezzella F., Morganti G., Ciaschetti G. (2008) A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research 35(10): 3202–3212
Pinedo M. (1995) Scheduling theory, algorithms, and systems. Prentice-Hall, Englewood Cliffs
Potts C. N., Strusevich V. A. (2009) Fifty years of scheduling: A survey of milestones. Journal of the Operational Research Society 60: S41–S68
Ramasesh R. (1990) Dynamic job shop scheduling: A survey of simulation research. Omega 18(1): 43–57
Saidi-Mehrabad M., Fattahi P. (2007) Flexible job shop scheduling with tabu search algorithms. International Journal of Advanced Manufacturing Technology 32(5–6): 563–570
Tay J. C., Ho N. B. (2008) Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problem. Computer & Industry Engineering 54(3): 453–473
Vieira G. E., Hermann J. W., Lin E. (2003) Rescheduling manufacturing systems: A framework of strategies, policies and methods. Journal of Scheduling 6(1): 39–62
Yin, W. J., Liu, M., & Wu, C. (2003). Learning single-machine scheduling heuristics subject to machine breakdowns with genetic programming. In R. Sarker et al. (Eds.), Proceeding of CEC2003: Congress on evolutionary computation (pp. 1050–1055). Canberra: IEEE Press. 9–12 December 2003.
Zandieh M., Mozaffari E., Gholami M. (2010) A robust genetic algorithm for scheduling realistic hybrid flexible flow line problems. Journal of Intelligent Manufacturing 21(6): 731–743
Zhang G. H., Shao X. Y., Li P. G., Gao L. (2009) An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers & Industrial Engineering 56(4): 1309–1318
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Nie, L., Gao, L., Li, P. et al. A GEP-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates. J Intell Manuf 24, 763–774 (2013). https://doi.org/10.1007/s10845-012-0626-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10845-012-0626-9