Scheduling a hybrid assembly-differentiation flowshop to minimize total flow time. (English) Zbl 1357.90061
Summary: This study considers a hybrid assembly-differentiation flowshop scheduling problem (HADFSP), in which there are three production stages, including components manufacturing, assembly, and differentiation. All the components of a job are processed on different machines at the first stage. Subsequently, they are assembled together on a common single machine at the second stage. At the third stage, each job of a particular type is processed on a dedicated machine. The objective is to find a job schedule to minimize total flow time (TFT). At first, a mixed integer programming (MIP) model is formulated and then some properties of the optimal solution are presented. Since the NP-hardness of the problem, two fast heuristics (SPT-based heuristic and NEH-based heuristic) and three hybrid meta-heuristics (HGA-VNS, HDDE-VNS and HEDA-VNS) are developed for solving medium- and large-size problems. In order to evaluate the performances of the proposed algorithms, a lower bound for the HADFSP with TFT criteria (HADFSP-TFT) is established. The MIP model and the proposed algorithms are compared on randomly generated problems. Computational results show the effectiveness of the MIP model and the proposed algorithms. The computational analysis indicates that, in average, the HDDE-VNS performs better and more robustly than the other two meta-heuristics, whereas the NEH heuristic consume little time and could reach reasonable solutions.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C11 | Mixed integer programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
scheduling; hybrid assembly-differentiation flowshop; hybrid meta-heuristics; total flow timeReferences:
| [1] | Al-Anzi, F. S.; Allahverdi, A., A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times, European Journal of Operational Research, 182, 1, 80-94 (2007) · Zbl 1128.90024 |
| [2] | Allahverdi, A.; Al-Anzi, F. S., Evolutionary heuristics and an algorithm for the two-stage assembly scheduling problem to minimize makespan with setup times, International Journal of Production Research, 44, 22, 4713-4735 (2006) · Zbl 1114.90373 |
| [3] | Allahverdi, A.; Al-Anzi, F. S., A pso and a tabu search heuristics for assembly scheduling problem of the two stage distributed database application, Computers & Operations Research, 33, 4, 1056-1080 (2006) · Zbl 1079.90045 |
| [4] | Allahverdi, A.; Al-Anzi, F. S., The two-stage assembly scheduling problem to minimize total completion time with setup times, Computer & Operations Research, 36, 10, 2740-2747 (2009) · Zbl 1160.90467 |
| [5] | Allahverdi, A.; Aydilek, H., Total completion time with makespan constraint in no-wait flowshops with setup times, European Journal of Operational Research, 238, 3, 724-734 (2014) · Zbl 1338.90156 |
| [6] | Brah, S. A.; Loo, L. L., Heuristics for scheduling in a flow shop with multiple processors, European Journal of Operations Research, 113, 1, 113-122 (1999) · Zbl 0933.90026 |
| [7] | Chen, S. H.; Chen, M. C., Addressing the advantages of using ensemble probabilistic models in Estimation of Distribution Algorithm for scheduling problems, International Journal of Production Economics, 141, 1, 24-33 (2013) |
| [8] | Chen, J. S.; Pan, J. C.H.; Lin, C. M., A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem, Expert Systems with Applications, 34, 1, 570-577 (2008) |
| [9] | Cheng, T. C.E.; Lin, B. M.T.; Tian, Y., Scheduling a two-stage differentiation flowshop to minimize weighted sum of machine completion times, Computers & Operations Research, 36, 11, 3031-3040 (2009) · Zbl 1162.90449 |
| [10] | Dorigo, M.; Gambardella, L. M., Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1, 1, 53-66 (1997) |
| [11] | Eglese, R. W., Simulated annealing: A tool for operational research, European Journal of Operational Research, 46, 3, 271-281 (1990) · Zbl 0699.90080 |
| [12] | Figielska, E., A heuristic for scheduling in a two-stage hybrid flowshop with renewable resources shared among the stages, European Journal of Operational Research, 236, 2, 433-444 (2014) · Zbl 1317.90117 |
| [13] | Framian, J. M.; Leistenb, R.; Ruiz-Usanoa, R., Efficient heuristics for flowshop sequencing with objectives of makespan and flowtime minimization, European Journal of Operational Research, 141, 3, 559-569 (2002) · Zbl 1081.90555 |
| [14] | Giovanni, L. D.; Pezzella, F., An improved genetic algorithm for the distributed and flexible job-shop scheduling problem, European Journal of Operational Research, 200, 2, 395-408 (2010) · Zbl 1177.90195 |
| [15] | Glover, F., Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, 13, 5, 533-549 (1996) · Zbl 0615.90083 |
| [16] | Hansen, P.; Mladenovic, N., Variable neighborhood search: Principles and applications, European Journal of Operational Research, 130, 3, 449-467 (2001) · Zbl 0981.90063 |
| [17] | Hauschild, M.; Pelikan, M., An introduction and survey of estimation of distribution algorithms, Swarm and Evolutionary Computation, 1, 3, 111-128 (2011) |
| [20] | Jarboui, B.; Eddaly, M.; Siarry, P., An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems, Computers & Operations Research, 36, 9, 2638-2646 (2009) · Zbl 1179.90138 |
| [21] | 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-320 (2007) |
| [22] | Koulamas, C.; Kyparisis, G. J., The three-stage assembly flowshop scheduling problem, Computers & Operations Research, 28, 7, 689-704 (2001) · Zbl 0990.90043 |
| [23] | Lee, C. Y.; Cheng, T. C.E.; Lin, B. M.T., Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem, Management Science, 39, 5, 616-625 (1993) · Zbl 0783.90054 |
| [24] | Lejeune, M. A., A variable neighborhood decomposition search method for supply chain management planning problems, European Journal of Operational Research, 175, 2, 959-976 (2006) · Zbl 1142.90424 |
| [25] | Li, W. D.; Ong, S. K.; Nee, A. Y.C., Optimization of process plans using a constraint-based tabu search approach, International Journal of Production Research, 42, 10, 1955-1985 (2004) · Zbl 1094.90535 |
| [26] | Liao, C. J.; Cheng, C. C., A variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date, Computers and Industrial Engineering, 52, 4, 404-413 (2007) |
| [27] | Lin, B. M.T.; Hwang, F. J., Total completion time minimization in a 2-stage differentiation flowshop with sequences per job type, Information Processing Letters, 111, 5, 208-212 (2011) · Zbl 1260.90091 |
| [28] | Liu, Y. C.; Fang, K. T.; Lin, B. M.T., A branch-and-bound algorithm for makespan minimization in differentiation flow shops, Engineering Optimization, 45, 12, 1397-1408 (2012) |
| [29] | Mladenovic, N.; Hansen, P., Variable neighborhood search, Computer & Operations Research, 24, 11, 1097-1100 (1997) · Zbl 0889.90119 |
| [30] | Montgomery, D. C., Design and analysis of experiments (2005), John Wiley and Sons: John Wiley and Sons Arizona · Zbl 1195.62128 |
| [31] | Mozdgir, A.; Fatemi Ghomi, S. M.T.; Jolai, F.; Navaei, J., Two-stage assembly flow-shop scheduling problem with non-identical assembly machines considering setup times, International Journal of Production Research (2013) |
| [33] | Murata, T.; Ishibuchi, H.; Tanaka, H., Genetic algorithms for flow shop scheduling problems, Computers & Operations Research, 30, 4, 1061-1071 (1996) |
| [34] | Naderi, B.; Ruiz, R., A scatter search algorithm for the distributed permutation flowshop scheduling problem, European Journal of Operational Research, 239, 2, 323-334 (2014) · Zbl 1339.90145 |
| [35] | Nawz, M.; Enscore, E. E.; Ham, I., A heuristic algorithm for the \(m\)-machine and \(n\)-job flowshop sequencing problem, Omega, 11, 1, 91-95 (1983) |
| [36] | Pan, Q. K.; Ruiz, R., An estimation of distribution algorithm for lot-streaming flow shop problems with setups, Omega - The International Journal of Management Science, 40, 2, 166-180 (2012) |
| [37] | Pinedo, M., Scheduling: Theory, algorithms and systems (2002), Prentice-Hall: Prentice-Hall Englewood cliffs, NJ · Zbl 1145.90394 |
| [38] | Potts, C. N.; Sevastjanov, S. V.; Strusevich, V. A.; Wassenhove, L. N.V.; Zwaneveld, C. M., The two stage assembly scheduling problem: complexity and approximation, Operations Research, 43, 2, 346-355 (1995) · Zbl 0837.90069 |
| [39] | Riane, F.; Artiba, A.; Elmaghraby, S. E., Sequencing a hybrid two-stage flowshop with dedicated machines, International Journal of Production Research, 40, 17, 4353-4380 (2002) · Zbl 1064.90545 |
| [40] | Roshanaei, V.; Naderi, B.; Jolai, F.; Khalili, M., A variable neighborhood search for job shop scheduling with set-up times to minimize makespan, Future Generation Computer Systems, 25, 6, 654-661 (2009) |
| [41] | Ruiz, R.; Maroto, C.; Alcaraz, J., Two new robust genetic algorithms for the flowshop scheduling problem, OMEGA - The International Journal of Management Science, 34, 5, 461-476 (2006) |
| [42] | Ruiz, R.; Stutzle, T., A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research, 177, 3, 2033-2049 (2007) · Zbl 1110.90042 |
| [43] | Ruiz, R.; Stutzle, T., An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives, European Journal of Operational Research, 187, 3, 1143-1159 (2008) · Zbl 1137.90514 |
| [45] | Storn, R.; Price, K., Differential evolution - A simple and efficient heuristic for global optimization over continuous space, Journal of Global Optimization, 11, 4, 341-359 (1997) · Zbl 0888.90135 |
| [46] | Tozkapan, A.; Kirca, O.; Chung, C. S., A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem, Computers & Operations Research, 30, 2, 309-320 (2003) · Zbl 1029.90031 |
| [47] | Tseng, L. Y.; Lin, Y. T., A hybrid genetic local search algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research, 198, 1, 84-92 (2009) · Zbl 1163.90532 |
| [48] | Wang, S. J.; Liu, M., A heuristic method for two-stage hybrid flow shop with dedicated machines, Computers & Operations Research, 40, 1, 438-450 (2013) · Zbl 1349.90413 |
| [49] | Wang, S. Y.; Wang, L.; Liu, M.; Xu, Y., An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem, International Journal of Production Economics, 145, 1, 387-396 (2013) |
| [50] | Wang, L.; Wang, S. R.; Xu, Y.; Zhou, G.; Liu, M., A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem, Computer & Industrial Engineering, 62, 4, 917-926 (2012) |
| [51] | Xing, K. Y.; Han, L. B.; Zhou, M. C.; Wang, F., Deadlock-free genetic scheduling algorithm for automotated manufacturing systems based on deadlock control policy, IEEE Transactions on System, Man and Cybernetics, Part B: Cybernetics, 42, 3, 603-615 (2012) |
| [52] | Yazdani, M.; Amiri, M.; Zandieh, M., Flexible job-shop scheduling with parallel variable neighborhood search algorithm, Expert Systems with Applications, 37, 1, 678-687 (2010) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
