The Distributed Assembly Parallel Machine Scheduling Problem with eligibility constraints

• Hatami, Sara ^[1] ; Ruiz García, Rubén ^[1] ; Romano, Carlos Andrés ^[1]
  1. [1] Universidad Politécnica de Valencia

     Universidad Politécnica de Valencia

     Valencia, España

     
• Localización: International Journal of Production Management and Engineering (IJPME), ISSN-e 2340-4876, ISSN 2340-5317, Vol. 3, Nº. 1, 2015, págs. 13-23
• Idioma: inglés
• DOI: 10.4995/ijpme.2015.3345
• Enlaces
  • Texto completo (pdf)
• Resumen

  • 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.

• Referencias bibliográficas
  • Chan, F. T. S., Chung, S. H., Chan, P. L. Y. (2005). An adaptive genetic algorithm with dominated genes for distributed scheduling problems....
  • 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:...
  • Elmaraghy, H., Schuh, G., ElMaraghy, W., Piller, F., Schönsleben, P., Tseng, M., Bernard, A. (2013). Product variety management. CIRP Annals-Manufacturing...
  • Fernandez-Viagas, V., Framinan, J.M. (2015). A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling...
  • Hariri, A. M. A., Potts, C. N. (1997). A branch and bound algorithm for the two-stage assembly scheduling problem. European Journal of Operational...
  • Hatami, S., Ruiz, R., Andrés-Romano, C. (2013). The distributed assembly permutation flowshop scheduling problem. International Journal of...
  • 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...
  • 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...
  • 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...
  • 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...
  • Lenstra, J. K., Rinnooy Kan, A. H. G., Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343–362....
  • Lin, S. W., Ying, K. C., Huang, C. Y. (2013). Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm....
  • Lin, Y., Li, W. (2004). Parallel machine scheduling of machine-dependent jobs with unit-length. European Journal of Operational Research,...
  • Mahdavi, I., Shirazi, B., Cho, N., Sahebjamnia, N., Ghobadi, S. (2008). Modeling an e-based real-time quality control information system in...
  • Naderi, B., Ruiz, R. (2010). The distributed permutation flowshop scheduling problem. Computers & Operations Research, 37(4): 754–768....
  • Naderi, B., Ruiz, R. (2014). A scatter search algorithm for the distributed permutation flowshop scheduling problem. European Journal of Operational...
  • Sluga, A., Butala, P., Bervar, G. (1998). A multi-agent approach to process planning and fabrication in distributed manufacturing. Computers...
  • Stafford, E. F., Tseng, F. T., Gupta, J. N. D. (2005). Comparative evaluation of MILP flowshop models. Journal of the Operational Research...
  • Sun, X., Morizawa, K., Nagasawa, H. (2003). Powerful heuristics to minimize makespan in fixed, 3-machine, assembly-type flowshop scheduling....
  • Sung, C. S., Kim, H. A. (2008). A two-stage multiple-machine assembly scheduling problem for minimizing sum of completion times. International...
  • Wang, S. Y., Wang, L., Liu, M., Xu, Y. (2013). An effective estimation of distribution algorithm for solving the distributed permutation flowshop...
  • Xiong, F., Xing, K., Wang, F., Lei, H., Han, L. (2014). Minimizing the total completion time in a distributed two stage assembly system with...