Abstract
Paradigms in modern production are shifting and pose new demands for optimization techniques. The emergence of new, versatile, reconfigurable and networked machines enables flexible manufacturing scenarios which require, in particular, planning and scheduling methods for cyber-physical production systems to be flexible, reasonably fast, and anytime. This paper presents an approach to flexible job-shop manufacturing scheduling with agent-based simulated trading, called shopST. Aspects of real manufacturing scheduling problems form the basis for a physical decomposition of the planning system into agents. The initial schedule created by the agents in shopST through reactive negotiation is successively improved through the exchange of resource binding constraints with an additional market agent. shopST is evaluated in comparison to selected other different solution approaches to flexible job-shop scheduling.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The source code for this project is publicly available at https://sourceforge.net/projects/shopst/.
References
Adams, J., Balas, E., Zawack, D.: The shifting bottleneck procedure for job shop scheduling. Manag. Sci. 34(3), 391–401 (1988)
Aydin, M.E., Oeztemel, E.: Dynamic job-shop scheduling using reinforcement learning agents. Robot. Auton. Syst. 33(2), 169–178 (2000)
Bachem, A., Hochstättler, W., Malich, M.: The simulated trading heuristic for solving vehicle routing problems. Discret. Appl. Math. 65(1–3), 47–72 (1996)
Bagheri, A., et al.: An artificial immune algorithm for the flexible job-shop scheduling problem. Future Gener. Comput. Syst. 26(4), 533–541 (2010)
Bellifemine, F., Poggi, A., Rimassa, G.: JADE-A FIPA-compliant agent framework. In: Proceedings of PAAM, vol. 99, London (1999)
Brandimarte, P.: Routing and scheduling in a flexible job shop by tabu search. Ann. Oper. Res. 41(3), 157–183 (1993)
Cohen, P.R., Cheyer, A., Wang, M., Baeg, S.C.: An open agent architecture. In: AAAI Spring Symposium, vol. 1 (1994)
Fattahi, P., Mehrabad, M.S., Jolai, F.: Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Intell. Manuf. 18(3), 331–342 (2007)
Gen, M., Lin, L.: Multiobjective evolutionary algorithm for manufacturing scheduling problems: state-of-the-art survey. Intell. Manuf. 25(5), 849–866 (2014)
Graham, R.L., et al.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. discret. Math. 5, 287–326 (1979)
Nouri, H.E., Driss, O.B., Ghédira, K.: A classification schema for the job shop scheduling problem with transportation resources: state-of-the-art review. In: Silhavy, R., Senkerik, R., Oplatkova, Z.K., Silhavy, P., Prokopova, Z. (eds.) Artificial Intelligence Perspectives in Intelligent Systems. AISC, vol. 464, pp. 1–11. Springer, Cham (2016). doi:10.1007/978-3-319-33625-1_1
Hsu, C.Y., Kao, B.R., Lai, K.R.: Agent-based fuzzy constraint-directed negotiation mechanism for distributed job shop scheduling. Eng. Appl. Artif. Intell. 53, 140–154 (2016)
Huang, S., et al.: Multi-objective flexible job-shop scheduling problem using modified discrete particle swarm optimization. SpringerPlus 5(1), 1432 (2016)
Hurink, J., Jurisch, B., Thole, M.: Tabu search for the job-shop scheduling problem with multi-purpose machines. Oper. Res. Spektrum 15(4), 205–215 (1994)
Kacem, I., Hammadi, S., Borne, P.: Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic. Math. Comput. Simul. 60(3), 245–276 (2002)
Kapahnke, P., Liedtke, P., Nesbigall, S., Warwas, S., Klusch, M.: ISReal: an open platform for semantic-based 3D simulations in the 3D internet. In: Patel-Schneider, P.F., Pan, Y., Hitzler, P., Mika, P., Zhang, L., Pan, J.Z., Horrocks, I., Glimm, B. (eds.) ISWC 2010. LNCS, vol. 6497, pp. 161–176. Springer, Heidelberg (2010). doi:10.1007/978-3-642-17749-1_11
Karageorgos, A., Mehandjiev, N., Weichhart, G., Hämmerle, A.: Agent-based optimisation of logistics and production planning. Eng. Appl. Artif. Intell. 16(4), 335–348 (2003)
Kirkpatrick, S., et al.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Leitao, P.: Agent-based distributed manufacturing control: a state-of-the-art survey. Eng. Appl. Artif. Intell. 22, 979–991 (2009)
Leitao, P., et al.: Smart agents in industrial cyber-physical systems. Proc. IEEE 104(5), 1086–1101 (2016)
Li, J., Pan, Q., Liang, Y.C.: An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems. Comput. Ind. Eng. 59(4), 647–662 (2010)
Li, J., Pan, Q., Xie, S.: An effective shuffled frog-leaping algorithm for multi-objective flexible job shop scheduling problems. Appl. Math. Comput. 218(18), 9353–9371 (2012)
Li, J.Q., Pan, Q., Gao, K.Z.: Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems. Adv. Manuf. Technol. 55(9), 1159–1169 (2011)
Pinedo, M.: Scheduling. Theory, Algorithms, and Systems. Springer, Cham (2016)
Pooja, D., Joshi, S.: Auction-based distributed scheduling in a dynamic job shop environment. Prod. Res. 40(5), 1173–1191 (2002)
Pruhs, K., Sgall, J., Torng, E.: Online scheduling. In: Handbook of Scheduling Algorithms, Models, and Performance Analysis. Chapman and Hall/CRC (2004)
Rossi, A., Dini, G.: Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method. Robot. Comput.-Integr. Manuf. 23(5), 503–516 (2007)
Wang, X., et al.: A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem. Adv. Manuf. Technol. 51(5), 757–767 (2010)
Weichhart, G., Hämmerle, A.: Multi-actor architecture for schedule optimisation based on lagrangian relaxation. In: Klusch, M., Unland, R., Shehory, O., Pokahr, A., Ahrndt, S. (eds.) MATES 2016. LNCS, vol. 9872, pp. 190–197. Springer, Cham (2016). doi:10.1007/978-3-319-45889-2_14
Xing, L.N., Chen, Y.W., Yang, K.W.: An efficient search method for multi-objective flexible job shop scheduling problems. J. Intell. Manuf. 20(3), 283–293 (2009)
Xing, L.N., et al.: A knowledge-based ant colony optimization for flexible job shop scheduling problems. Appl. Soft Comput. 10(3), 888–896 (2010)
Yeoh, W., Felner, A., Koenig, S.: BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, vol. 2. IFMAS (2008)
Zhang, G., Gao, L., Shi, Y.: An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Syst. Appl. 38(4), 3563–3573 (2011)
Acknowledgements
The work described in this paper was partially funded by the German Federal Ministry of Education and Research (BMBF) in the project INVERSIV and the European Commission in the project CREMA.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Nedwed, F.Y., Zinnikus, I., Nukhayev, M., Klusch, M., Mazzola, L. (2017). shopST: Flexible Job-Shop Scheduling with Agent-Based Simulated Trading. In: Berndt, J., Petta, P., Unland, R. (eds) Multiagent System Technologies. MATES 2017. Lecture Notes in Computer Science(), vol 10413. Springer, Cham. https://doi.org/10.1007/978-3-319-64798-2_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-64798-2_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-64797-5
Online ISBN: 978-3-319-64798-2
eBook Packages: Computer ScienceComputer Science (R0)