Abstract
This paper considers multiprocessor task scheduling in a multistage hybrid flow-shop environment. The problem even in its simplest form is NP-hard in the strong sense. The great deal of interest for this problem, besides its theoretical complexity, is animated by needs of various manufacturing and computing systems. We propose a new approach based on limited discrepancy search to solve the problem. Our method is tested with reference to a proposed lower bound as well as the best-known solutions in literature. Computational results show that the developed approach is efficient in particular for large-size problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Beck, J.C., Perron, L.: Discrepancy-bounded depth first search. In: Proceedings of CPAIOR 2000, pp. 8–10 (2000)
Ben Hmida, A., Haouari, M., Huguet, M.-J., Lopez, P.: Solving two-stage hybrid flow shop using climbing depth-bounded discrepancy search. Computers and Industrial Engineering 60(2), 320–327 (2010)
Ben Hmida, A., Huguet, M.-J., Lopez, P., Haouari, M.: Climbing depth-bounded discrepancy search for solving hybrid flow shop scheduling problems. European Journal of Industrial Engineering 1(2), 223–243 (2007)
Bertel, S., Billaut, J.-C.: A genetic algorithm for an industrial multiprocessor flow shop scheduling problem with recirculation. European Journal of Operational Research 159(3), 651–662 (2004)
Brooks, G., White, C.: An algorithm for finding optimal or near optimal solutions to the production scheduling problem. Journal of Industrial Engineering 16, 34–40 (1965)
Chen, J., Lee, C.-Y.: General multiprocessor task scheduling. Naval Research Logistics 46, 57–74 (1999)
Dongarra, J.: Performance of various computers using standard linear equations software. Technical report, University of Tennessee (2009)
Ercan, M.F., Fung, Y.-F.: Real-time image interpretation on a multi-layer architecture. In: Proceedings of IEEE TENCON 1999, pp. 1303–1306 (1999)
Fischetti, M., Lodi, A.: Local branching. Mathematical Programming 98, 23–47 (2003)
Harvey, W.D., Ginsberg, M.L.: Limited discrepancy search. In: Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI 1995), Montréal, Québec, Canada, vol. 1, pp. 607–615 (August 1995)
Jouglet, A., Oğuz, C., Sevaux, M.: Hybrid flow-shop: a memetic algorithm using constraint-based scheduling for efficient search. Journal of Mathematical Modelling and Algorithms 8, 271–292 (2009)
Kelley Jr, J.E.: The critical-path method: Resources planning and scheduling. In: Thompson, G.L., Muth, J.F. (eds.) Industrial Scheduling, pp. 347–365. Prentice-Hall, Englewood Cliffs (1963)
Kiziltan, Z., Lodi, A., Milano, M., Parisini, F.: CP-based local branching. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 847–855. Springer, Heidelberg (2007)
Korf, R.E.: Improved limited discrepancy search. In: Proceedings of the 13th National Conference on Artificial Intelligence (AAAI 1996), Portland, OR, vol. 1, pp. 286–291 (August 1996)
Milano, M., Roli, A.: On the relation between complete and incomplete search: an informal discussion. In: Proceedings of CPAIOR 2002, Le Croisic, France, pp. 237–250 (2002)
Oğuz, C., Ercan, M.F.: A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks. Journal of Scheduling 8, 323–351 (2005)
Oğuz, C., Fung, Y.-F., Ercan, M.F., Qi, X.-T.: Parallel genetic algorithm for a flow shop problem with multiprocessor tasks. In: International Conference on Computational Science, Berlin, Heidelberg, pp. 548–559 (2003)
Oğuz, C., Zinder, Y., Ha Do, V., Janiak, A., Lichtenstein, M.: Hybrid flow shop scheduling problems with multiprocessor task systems. European Journal of Operational Research 152, 115–133 (2004)
Prosser, P., Unsworth, C.: LDS: testing the hypothesis. Technical Report DCS TR-2008-273, Dept of Computing Science, University of Glasgow (2008)
Şerifoğlu, F.S., Ulusoy, G.: Multiprocessor task scheduling in multistage hybrid flow-shops: A genetic algorithm approach. European Journal of Operational Research 55(5), 504–512 (2004)
Şerifoğlu, F.S., Ulusoy, G.: Multiprocessor task scheduling in multistage hybrid flow-shops: An ant colony system approach. International Journal of Production Research 44(16), 3161–3177 (2006)
Sprecher, A., Kolisch, R., Drexl, A.: Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem. European Journal of Operational Research 80(1), 94–102 (1995)
Walsh, T.: Depth-bounded discrepancy search. In: Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI 1997), Nagoya, Japan, vol. 2, pp. 1388–1395 (August 1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lahimer, A., Lopez, P., Haouari, M. (2011). Climbing Depth-Bounded Adjacent Discrepancy Search for Solving Hybrid Flow Shop Scheduling Problems with Multiprocessor Tasks. In: Achterberg, T., Beck, J.C. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2011. Lecture Notes in Computer Science, vol 6697. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21311-3_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-21311-3_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21310-6
Online ISBN: 978-3-642-21311-3
eBook Packages: Computer ScienceComputer Science (R0)