The Distributed Assembly Parallel Machine Scheduling Problem with eligibility constraints.

Sara Hatami, Rubén Ruiz García, Carlos Andrés Romano


In this paper we jointly consider realistic scheduling extensions: First we study the distributed unrelated parallel machines problems by which there is a set of identical factories with parallel machines in a production stage. Jobs have to be assigned to factories and to machines. Additionally, there is an assembly stage with a single assembly machine. Finished jobs at the manufacturing stage are assembled into final products in this second assembly stage. These two joint features are referred to as the distributed assembly parallel machine scheduling problem or DAPMSP. The objective is to minimize the makespan in the assembly stage. Due to technological constraints, machines cannot be left empty and some jobs might be processed on certain factories only. We propose a mathematical model and two high performing heuristics. The model is tested with two state-of-the-art solvers and, together with the heuristics, 2220 instances are solved in a comprehensive computational experiments. Results show that the proposed model is able to solve moderately-sized instances and one of the heuristics is fast, giving close to optimal solutions in less than half a second in the worst case.


Distributed parallel machines; Assembly stage; Heuristics; Model

Full Text:



Chan, F. T. S., Chung, S. H., Chan, P. L. Y. (2005). An adaptive genetic algorithm with dominated genes for distributed scheduling problems. Expert Systems with Applications, 29(2): 364–371. doi:10.1016/j.eswa.2005.04.009

Chan, F. T. S., Chung, S. H., Chan, P. L. Y., Finke, G., Tiwari, M. K. (2006). Solving distributed FMS scheduling problems subject to maintenance: genetic algorithms approach. Robotics and Computer-Integrated Manufacturing, 22(5-6): 493–504. doi:10.1016/j.rcim.2005.11.005

Elmaraghy, H., Schuh, G., ElMaraghy, W., Piller, F., Schönsleben, P., Tseng, M., Bernard, A. (2013). Product variety management. CIRP Annals-Manufacturing Technology, 62(2): 629–652. doi:10.1016/j.cirp.2013.05.007

Fernandez-Viagas, V., Framinan, J.M. (2015). A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem. International Journal of Production Research, 53(4): 1111–1123. doi:10.1080/00207543.2014.948578

Hariri, A. M. A., Potts, C. N. (1997). A branch and bound algorithm for the two-stage assembly scheduling problem. European Journal of Operational Research, 103(3): 547–556. doi:10.1016/S0377-2217(96)00312-8

Hatami, S., Ruiz, R., Andrés-Romano, C. (2013). The distributed assembly permutation flowshop scheduling problem. International Journal of Production Research, 51: 5292–5308. doi:10.1080/00207543.2013.807955

Jia, H. Z., Fuh, J. Y. H., Nee, A. Y. C., Zhang, Y. F. (2002). Web-based multi-functional scheduling system for a distributed manufacturing environment. Concurrent Engineering: Research and Applications, 10(1): 27–39.

Jia, H. Z., Nee, A. Y. C., Fuh, J. Y. H., Zhang, Y. F. (2003). A modified genetic algorithm for distributed scheduling problems. Journal of Intelligent Manufacturing, 14(3-4): 351–362. doi:10.1023/A:1024653810491

Jia, H. Z., Fuh, J. Y. H., Nee, A. Y. C., Zhang, Y. F. (2007). Integration of genetic algorithm and Gantt chart for job shop scheduling in distributed manufacturing systems. Computers & Industrial Engineering, 53(2): 313–320. doi:10.1016/j.cie.2007.06.024

Lee, C. Y., Cheng, T. C. E., Lin, B. M. T. (1993). Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. Management Science, 39(5): 616–625. doi:10.1287/mnsc.39.5.616

Lenstra, J. K., Rinnooy Kan, A. H. G., Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343–362. doi:10.1016/S0167-5060(08)70743-X

Lin, S. W., Ying, K. C., Huang, C. Y. (2013). Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm. International Journal of Production Research, 51(16): 5029–5038. doi:10.1080/00207543.2013.790571

Lin, Y., Li, W. (2004). Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research, 156(1): 261–266. doi:10.1016/S0377-2217(02)00914-1

Mahdavi, I., Shirazi, B., Cho, N., Sahebjamnia, N., Ghobadi, S. (2008). Modeling an e-based real-time quality control information system in distributed manufacturing shops. Computers in Industry, 59(8): 759–766. doi:10.1016/j.compind.2008.03.005

Naderi, B., Ruiz, R. (2010). The distributed permutation flowshop scheduling problem. Computers & Operations Research, 37(4): 754–768. doi:10.1016/j.cor.2009.06.019

Naderi, B., Ruiz, R. (2014). A scatter search algorithm for the distributed permutation flowshop scheduling problem. European Journal of Operational Research, 239(2): 323–334. doi:10.1016/j.ejor.2014.05.024

Sluga, A., Butala, P., Bervar, G. (1998). A multi-agent approach to process planning and fabrication in distributed manufacturing. Computers & Industrial Engineering, 35(3-4): 455–458. doi:10.1016/S0360-8352(98)00132-6

Stafford, E. F., Tseng, F. T., Gupta, J. N. D. (2005). Comparative evaluation of MILP flowshop models. Journal of the Operational Research Society, 56(1): 88–101. doi:10.1057/palgrave.jors.2601805

Sun, X., Morizawa, K., Nagasawa, H. (2003). Powerful heuristics to minimize makespan in fixed, 3-machine, assembly-type flowshop scheduling. European Journal of Operational Research, 146(3): 499–517. doi:10.1016/S0377-2217(02)00245-X

Sung, C. S., Kim, H. A. (2008). A two-stage multiple-machine assembly scheduling problem for minimizing sum of completion times. International Journal of Production Economics, 113(2): 1038–1048. doi:10.1016/j.ijpe.2007.12.007

Wang, S. Y., Wang, L., Liu, M., Xu, Y. (2013). An effective estimation of distribution algorithm for solving the distributed permutation flowshop scheduling problem. International Journal of Production Economics, 145(1): 387–396. doi:10.1016/j.ijpe.2013.05.004

Xiong, F., Xing, K., Wang, F., Lei, H., Han, L. (2014). Minimizing the total completion time in a distributed two stage assembly system with setup times. Computers & Operations Research, 47: 92–105. doi:10.1016/j.cor.2014.02.005

Abstract Views

Metrics Loading ...

Metrics powered by PLOS ALM


Cited-By (articles included in Crossref)

This journal is a Crossref Cited-by Linking member. This list shows the references that citing the article automatically, if there are. For more information about the system please visit Crossref site

1. Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures
Jose M. Framinan, Paz Perez-Gonzalez, Victor Fernandez-Viagas
European Journal of Operational Research  vol: 273  issue: 2  first page: 401  year: 2019  
doi: 10.1016/j.ejor.2018.04.033

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives- 4.0 International License 

Universitat Politècnica de València

e-ISSN: 2340-4876     ISSN: 2340-5317