The Distributed Assembly Parallel Machine Scheduling Problem with eligibility constraints.
Submitted: 2014-10-29
|Accepted: 2015-01-07
|Published: 2015-01-25
Downloads
Keywords:
Distributed parallel machines, Assembly stage, Heuristics, Model
Supporting agencies:
Spanish Ministry of Economy and Competitiveness
“RESULT-Realistic Extended Scheduling Using Light Techniques” (No. DPI2012- 36243-C02-01) and “Hybrid Methods for Horizontal Cooperation in Green Transportation and Logistics GreenCOOP” TRA2013-48180-C3-3-P
Abstract:
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.
References:
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 modiï¬ed 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 modiï¬ed 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 ï¬xed, 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
