Skip to main content
SpringerLink
Log in

Network modeling and evolutionary optimization for scheduling in manufacturing

  • Published:
Journal of Intelligent Manufacturing Aims and scope Submit manuscript

Abstract

Scheduling is one of the most important fields in Advanced Planning and Scheduling or a manufacturing optimization. In this paper, we propose a network modeling technique to formulate the complex scheduling problems in manufacturing, and focus on how to model the scheduling problems to mathematical formulation. We propose a multi-section evolutionary algorithm for the scheduling models formulated by network modeling. Through a combination of the network modeling and this multi-section evolutionary algorithm, we can implement the auto-scheduling in the manufacturing system. The effectiveness and efficiency of proposed approach are investigated with various scales of scheduling problems by comparing with recent related researches. Lastly, we introduced service-oriented evolutionary computation architecture software. It help improved the evolutionary computation’s availability in the variable practical scheduling in manufacturing.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Adams J., Balas E., Zawack D. (1988) The shifting bottleneck procedure for job shop scheduling. Management Science 34: 391–401

    Article  Google Scholar 

  • Balas E. (1969) Machine scheduling via disjunctive graphs: An implicit enumeration algorithm. Operation Research 17: 941–957

    Article  Google Scholar 

  • Bell M. (2008) Introduction to service-oriented modeling. service-oriented modeling: Service analysis, design, and architecture. Wiley, New York, p 3

    Google Scholar 

  • Bermudez, J. (1998). Advanced Planning and Scheduling: Is it as good as it sounds? The report on Supply Chain Management, March, 3–18.

  • Bidot J., Vidal T., Laborie P., Beck J. C. (2009) A theoretic and practical framework for scheduling in a stochastic environment. Journal of Scheduling 12(3): 315–344

    Article  Google Scholar 

  • Boudia M., Prins C. (2009) A memetic algorithm with dynamic population management for an integrated production-distribution problem. European Journal of Operational Research 195(3): 703–715

    Article  Google Scholar 

  • Brandimarte P. (1993) Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research 41: 157–183

    Article  Google Scholar 

  • Bruker P., Schlie R. (1990) Job-shop scheduling with multi-purpose machines. Computing 45: 369–375

    Article  Google Scholar 

  • Cheng R., Gen M., Tsujimura Y. (1996) A tutorial survey of job-shop scheduling problems using genetic algorithm, Part I: Representation. Computers and Industrial Engineering 30(4): 983–997

    Article  Google Scholar 

  • Cheng R., Gen M., Tsujimura Y. (1999) A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: Hybrid genetic search strategies. Computers and Industrial Engineering 36(2): 343–364

    Article  Google Scholar 

  • Dechter R., Meiri I., Pearl J. (1991) Temporal constraint networks. Artificial Intelligence 49(1–3): 61–95

    Article  Google Scholar 

  • Dellaert N., Jeunet J., Jornard N. (2000) A genetic algorithm to solve the general multi-level lot-sizing problem with time-varying costs. International Journal of Production Economy 68: 241–257

    Article  Google Scholar 

  • Eck, M. (2003). Advanced planning and scheduling. BWI paper: http://obp.math.vu.nl/logistics/papers/vaneck.doc.

  • Erl T. (2005) Service-oriented architecture: Concepts, technology, and design. Prentice Hall PTR, Upper Saddle River

    Google Scholar 

  • Fisher H. (1963) Probabilistic learning combinations of local job-shop scheduling rules. In: Muth J. F., Thompson G. L. (eds) Industrial scheduling. Prentice Hall, Englewood Cliffs, pp 225–251

    Google Scholar 

  • Floudas C. A., Lin X. (2004) Continuous-time versus discrete-time approaches for scheduling of chemical processes: A review. Computers & Chemical Engineering 28: 2109

    Article  Google Scholar 

  • Floudas C. A., Lin X. (2005) Mixed integer linear programming in process scheduling: Modeling, algorithms, and applications. Annals of Operations Research 139: 131

    Article  Google Scholar 

  • Gen M., Cheng R., Lin L. (2008) Network models and optimization: Multiobjective genetic algorithm approach. Springer, London

    Google Scholar 

  • Gen M., Lin L., Zhang H. (2009) Evolutionary techniques for optimization problems in integrated manufacturing system: State-of-the-art-survey. Computers and Industrial Engineering 56(3): 779–808

    Article  Google Scholar 

  • Gen, M., Tsujimura, Y., & Kubota, E. (1997). Solving job-shop scheduling problem using genetic algorithms. In Proceedings of the 16th international conference on computers & industrial engineering (pp. 576–579).

  • Gen, M., & Zhang, H. (2006, November). Effective designing chromosome for optimizing advanced planning and scheduling. In C. H. Dagli, et al. (Eds.), Intelligent engineering systems through artificial neural networks (Vol. 16, pp. 61–66). New York: ASME Press.

  • Grabot B., Geneste L. (1994) Dispatching rules in scheduling: A fuzzy approach. International Journal of Production Research 32(4): 903–915

    Article  Google Scholar 

  • Kacem I., Hammadi S., Borne P. (2002) Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man, and Cybernetics-Part C 32(1): 1–13

    Article  Google Scholar 

  • Kim Y., Park K., Ko J. (2003) A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling. Computers and Operations Research 30: 1151–1171

    Article  Google Scholar 

  • Kung L.-C., Chern C.-C. (2009) Heuristic factory planning algorithm for advanced planning and scheduling. Computers & Operations Research 36(9): 2513–2530

    Article  Google Scholar 

  • Lee C. Y., Chen Z. L. (2001) Machine scheduling with transportation considerations. Journal of Scheduling 4: 3–24

    Article  Google Scholar 

  • Lin L., Gen M. (2009a) Priority-based genetic algorithm for shortest path routing problem in OSPF. Studies in Computational Intelligence 187: 91–103

    Article  Google Scholar 

  • Lin L., Gen M. (2009b) Auto-tuning strategy for evolutionary algorithms: Balancing between exploration and exploitation. Soft Computing 13(2): 157–168

    Article  Google Scholar 

  • Lin L., Shinn S. W., Gen M., Hwang H. (2006) Network model and effective evolutionary approach for AGV dispatching in manufacturing system. Journal of Intelligent Manufacturing 17(4): 465–477

    Article  Google Scholar 

  • Lopez O., Ramirez M. (2005) A STEP-based manufacturing information system to share flexible manufacturing resources data. Journal of Intelligent Manufacturing 16(3): 287–301

    Article  Google Scholar 

  • Mati Y., Rezg N., Xie X. (2001) An integrated greedy heuristic for a flexible job shop scheduling problem. IEEE International Conference on Systems, Man, and Cybernetics 4: 2534–2539

    Google Scholar 

  • Michael, C. M., Stewart, C. V., & Kelly, R. B. (1991). Reducing the search time of a steady state genetic algorithm using the immigration operator. In Proceedings of IEEE international conference tools for AI (pp. 500–501).

  • Moon C., Kim J. S., Gen M. (2004) Advanced planning and scheduling based on precedence and resource constraints for e-plant chains. International Journal of Production Research 42(15): 2941–2955

    Article  Google Scholar 

  • Najid, N. M., Dauzere-Peres, S., & Zaidat, A. (2002). A modified simulated annealing method for flexible job shop scheduling problem. IEEE International Conference on Systems, Man and Cybernetics, 5(6).

  • Nowicki E., Smutnicki C. (2005) An advanced tabu search algorithm for the job-shop problem. Journal of Scheduling 8(2): 145–159

    Article  Google Scholar 

  • Okamoto, A., Gen, M., & Sugawara, M. (2005a). Cooperation of scheduling agent and transportation agent in APS system. In Proceedings of the J.S.L.S. Kyushu Division Conference (pp. 1–11) (in Japanese).

  • Okamoto, A., Gen, M., & Sugawara, M. (2005b). APS system based on scheduler moGA & XML. Journal of the Society of Plant Engineers Japan, 17(2), 15–24 (in Japanese).

    Google Scholar 

  • Okamoto A., Gen M., Sugawara M. (2006a) Integrated data structure and scheduling approach for manufacturing and transportation using hybrid multistage operation-based genetic algorithm. Journal of Intelligent Manufacturing 17: 411–421

    Article  Google Scholar 

  • Okamoto A., Gen M., Sugawara M. (2006b) Integrated scheduling problem of manufacturing & transportation with pickup & delivery. International Journal of Logistics and SCM Systems 1: 19–27

    Google Scholar 

  • Raa B., Aghezzaf E. H. (2005) A robust dynamic planning strategy for lot-sizing problems with stochastic demands. Journal of Intelligent Manufacturing 16(2): 207–213

    Article  Google Scholar 

  • Roy, B., & Sussmann, B. (1964). Les problems d’ordonnancement avec contraintes disjunctives. Note D.S. no.9 bis, SEMA, Paris, France.

  • Soukhal A., Oulamara A., Martineau P. (2005) Complexity of flow shop scheduling problems with transportation constraints. European Journal of Operational Research 161: 32–41

    Article  Google Scholar 

  • Tan W. (2000) Integration of process planning and scheduling—a review. Journal of Intelligent Manufacturing 11(1): 51–63

    Article  Google Scholar 

  • Tan W. (2004) A linearized polynomial mixed integer programming model for the integration of process planning and scheduling. Journal of Intelligent Manufacturing 15(5): 593–605

    Article  Google Scholar 

  • Tavakkoli-Moghaddam R., Jolai F., Vaziri F., Ahmed P.K., Azaron A. (2005) A hybrid method for solving stochastic job shop scheduling problems. Applied Mathematics and Computation 170(1): 185–206

    Article  Google Scholar 

  • Verderame P. M., Christodoulos A. F. (2008) Integrated operational planning and medium-term scheduling for large-scale industrial batch plants. Industrial & Engineering Chemistry Research 47(14): 4845–4860

    Article  Google Scholar 

  • Wu Z., Chien C. F. (2008) Modeling semiconductor testing job scheduling and dynamic testing machine configuration. Expert Systems with Applications 35(1): 485–496

    Article  Google Scholar 

  • Wu Z., Weng M. X. (2005) Multiagent scheduling method with earliness and tardiness objectives in flexible job shops. IEEE Transactions on System, Man, and Cybernetics-Part B 35(2): 293–301

    Article  Google Scholar 

  • Xia W., Wu Z. (2005) An effective hybrid optimization approach for muti-objective flexible job-shop scheduling problem. Computers & Industrial Engineering 48: 409–425

    Article  Google Scholar 

  • Yang S., Wang D. (2000) Constraint satisfaction adaptive neural network and heuristics combined approaches for generalized job-shop scheduling. IEEE Transactions on Neural Networks 11(2): 474–486

    Article  Google Scholar 

  • Zhang H., Gen M. (2005) Multistage-based genetic algorithm for flexible job-shop scheduling problem. Journal of Complexity International 11: 223–232

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Software, Dalian University of Technology, Dalian, China

    Lin Lin

  2. Fuzzy Logic Systems Institute, Iizuka, Fukuoka, Japan

    Lin Lin & Mitsuo Gen

  3. Graduate School of Information, Production and Systems, Waseda University, Kitakyushu-shi, Fukuoka, Japan

    Xin-Chang Hao

  4. Hanyang University, Ansan, Korea

    Mitsuo Gen

  5. Division of Computer and Information Engineering, Dongseo University, Busan, Korea

    Jung-Bok Jo

Authors
  1. Lin Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xin-Chang Hao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mitsuo Gen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jung-Bok Jo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jung-Bok Jo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lin, L., Hao, XC., Gen, M. et al. Network modeling and evolutionary optimization for scheduling in manufacturing. J Intell Manuf 23, 2237–2253 (2012). https://doi.org/10.1007/s10845-011-0569-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10845-011-0569-6

Keywords

Search

Navigation