Agent-based approach for cooperative scheduling

Document Type : Research Paper


Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran


This paper studies the multi-factory production (MFP) network scheduling problem where a number of different individual factories join together to form a MFP network, in which these factories can operate more economically than operating individually. However, in such network which known as virtual production network with self-interested factories with transportation times, each individual factory usually focuses on self-benefits and does not care much about the others within the network. We first described the realistic features which incorporate in problem definition. Then two different variants of the problem are considered. In the first case, we propose approximation algorithms with the best achievable theoretical guarantee in three cases: (i) all factories are interested in the makespan, (ii) all factories are interested in the sum of completion times, and (iii) the case in which among allfactories, some factories are interested in the sum of completion times and the others are interested in the makespan. Furthermore, with considering the transpiration, we model the problem as a mixed integer linear programming to minimize the makespan and total completion time and solve it by CPLEX solver to obtain Pareto solutions by applying modified ϵ -constraint approach. Experiments show that this procedure is capable of producing good results to approximate the efficient set.


Main Subjects

Agnetis, A., Mirchandani, P., Pacciarelli, D., Pacifici, A.: Scheduling problems with two competing agents. Operations Research 52, 229–242 (2004)
Bartlett, C.A., Ghoshal, S.: Managing across borders: the transnational solution. Second Edition, HBS Press, Boston, MA (1998)
Chan, F.T.S., Chung, S.H.: Distributed Scheduling in Multiple-factory Production with Machine Maintenance, In: Wang, L. Shen, W. (eds.), Process Planning and Scheduling for Distributed Manufacturing, pp. 243-267. London, Springer Series in Advanced Manufacturing (2007)
Chung, S.H., Chan, F.T.S., Chan, H.K.: A modified genetic algorithm approach for scheduling of perfect maintenance in distributed production scheduling, Engineering Applications of Artificial Intelligence 22, 1005–1014 (2009)
Dessouky, M.M.: Scheduling identical jobs with unequal ready times on uniform parallel machines to minimize the maximum lateness, Computers & Industrial Engineering 34, 793–806 (1998)
Diedrich, F., Jansen, K., Pascual, F., Trystram, D.: Approximation algorithms for scheduling with reservations, Algorithmica 58, 391–404 (2010)
Flaherty, M.T.: Coordinating international manufacturing and technology. In: Porter, M.E. (ed.), Competition in Global Industries. Harvard Business School Press (1989)
Fleury, A., Fleury, M.T.: Competitive strategies and core competencies: perspectives for the internationalization of industry in Brazil. Integrated Manufacturing Systems 14 (1), 16–25 (2003)
Granot, F., Skorin-Kapov, J., Tamir, A.: Using quadratic programming to solve high multiplicity scheduling problems on parallel machines, Algorithmica 17, 100-110 (1997)
Jia, H.Z., Fuh, J.Y.H., Nee, A.Y.C., Zhang, Y.F. Integration of genetic algorithm and Gantt chart for job shop scheduling in distributed manufacturing systems, Computers & Industrial Engineering 53(2), 313–20 (2007)
Jia, H.Z., Fuh, J.Y.H., Nee, A.Y.C., Zhang, Y.F.: Web-based multi-functional scheduling system for a distributed manufacturing environment, Concurrent Engineering-Research and Applications 10(1), 27–39 (2002)
Johansen, K., Comstock, M., Winroth, M.: Coordination in collaborative manufacturing mega-networks: A case study, Journal of Engineering and Technology Management 22 (3), 226-244 (2005)
Karatza, H.D.: Job scheduling in heterogeneous distributed systems, The Journal of Systems and Software 56, 203-212 (2001)
Khurana, A., Talbot, B.: Plant missions in global manufacturing networks: A resource-based view with evidence from the global color picture tube industry. Working Paper 99–0005. University of Michigan Business School (1999)
Li, X., Shi, Y., Gregory, M.J.: Global manufacturing virtual network (GMVN) and its position in the spectrum of strategic alliance, EurOMA 7th International Annual Conference, pp. 330-337. Ghent, Belgium (2000)
Lin, H.K., Harding, J.A., Shahbaz, M.: Manufacturing system engineering ontology for semantic interoperability across extended project teams. International Journal of Production Research 42(24), 5099-5118 (2004)
Loeser, B.O.: How to set up a cooperation network in the production industry-example of the Huber + Suhner AG. Industrial Marketing Management 28, 453–465 (1999)
Mavrotas, G.: Effective implementation of the e-constraint method in multi-objective mathematical programming problems, Applied Mathematics and Computation 213, 455–465 (2009)
Miettinen, K.M.: Nonlinear Multiobjective Optimization. First Edition, Kluwer Academic, Boston(1999)
Monroy, C.R., Vilana Arto, J.R.: Analysis of global manufacturing virtual networks in the aeronautical industry. International Journal of Production Economics 126, 314–323 (2010)
Naderi, B., Ruiz, R.: The distributed permutation flowshop scheduling problem, Computers & Operations Research 37, 754-768 (2010)
Neiman, D.E., Lesser, V.R.: A Cooperative Repair Method for a Distributed Scheduling System, in: Drabble, B. (eds.), International Conference on Artificial Intelligence Planning Systems (AIPS), pp. 166-173. Edinburg, Scotland, Menlo Park (1996)
Pinedo, M.L.: Scheduling Theory, Algorithms, and Systems. Third Edition, Springer, NY (2008)
Sandholm, T.W.: Automated contracting in distributed manufacturing among independent companies, Journal of Intelligent Manufacturing 11, 271–283 (2000)
Saule, E., Trystram, D.: Multi-users scheduling in parallel systems, Parallel & Distributed Processing, 2009. IPDPS 2009, IEEE International Symposium on, 23-29 May 2009, pp. 1 – 9 (2009)
Shakhlevich, N.V., Strusevich, V.A.: Preemptive scheduling on uniform parallel machines with controllable job processing times, Algorithmica 51( 4), 451-473 (2008)
Shi, Y., Fleet, D., Gregory, M.: Global manufacturing virtual network and its position in manufacturing systems. The 7th Annual International Manufacturing Symposium, Institute for Manufacturing, Department of Engineering, University of Cambridge (2005)
Shi, Y., Gregory, M.: From original equipment manufacturers to total solution providers: An emergence of global manufacturing virtual network in electronics industry. International Journal of Service Technology and Management 4 (4-6), 331-346 (2003)
Shi, Y., Gregory, M.: International manufacturing networks—to develop global competitive capabilities. Journal of Operations Management 16, 195–214 (1998)
Sturgeon, T., Florida, R.: Globalization and jobs in the automotive Industry. Center for Technology Policy, and Industrial Development, Massachusetts Institute of Technology, Cambridge (1999)
T’Kindt, V., Billaut, J.: Multicriteria Scheduling: Theory, Models and. Algorithms, Second Edition, Springer, Berlin (2006)
Tuma, A.: Configuration and coordination of virtual production networks, International Journal of Production Economics 5657, 641-648 (1998)
Vercellis, C.: Multi-plant production planning in capacitated self-configuring two-stage serial systems, European Journal of Operational Research 119, 451-460 (1999)
Vilana, J.R., Monroy, C.R.: Structure and relationships within global manufacturing virtual networks. Intangible Capital 5(2), 152-168 (2009)
Wiendahl, H.P., Helms, K., Lutz, S.: Supply Net–New Methods for Capacity Flexibilisation in Production Networks, in: Maropoulos, P. G., McGeough, J. A. (eds.), Proceedings of the 15th International Conference on Computer-Aided Production Engineering, pp. 609 – 614. UK, Durham (1999)
Williams, J.F.: Heuristic techniques for simultaneous scheduling of production and distribution in multi-echelon structures: Theory and empirical comparisons, Management Science 27, 336-352 (1981)
You, F., Grossmann, I.E.: Design of responsive supply chains under demand uncertainty, Computers and Chemical Engineering 32(12), 3090-3111 (2008)
Zhang, W., Gen, M.: Process planning and scheduling in distributed manufacturing system using multiobjective genetic algorithm, IEEJ Transactions on Electrical and Electronic Engineering 5, 62–72 (2010)
Zhang, Y., Li, L., Wang, H., Zhao, Y., Guo, X., Meng, C.: Approach to the distributed job shop scheduling based on multi-agent, In: IEEE International Conference on Automation and Logistics, Qingdao, pp. 2031 – 2034 (2008)