ارائه الگوریتم شاخه و برش برای حل مساله زمانبندی تولید کارگاهی با استفاده از نامعادلات معتبر

نوع مقاله : مقاله پژوهشی

نویسندگان

1 گروه مهندسی صنایع، دانشگاه بوعلی سینا

2 گروه مهندسی صنایع، ددانشگاه بوعلی سینا

چکیده

در این مقاله مساله زمانبندی تولید کارگاهی در نظر گرفته شده که در عین کاربردی بودن آن به عنوان یکی از مسائل پیچیده در مبحث بهینه‌سازی ترکیبیاتی مطرح بوده و این امر باعث توجه روز افزون محققین به این مساله شده است. در این مساله با فرض وجود تعدادی کارگاه، تعداد کار بایستی با مسیر تولیدی که از قبل معلوم است در این کارگاهها پردازش ‌شوند. به منظور حل این مساله، در این مقاله، ابتدا مساله زمانبندی تولید کارگاهی بصورت برنامه‌ریزی عددصحیح مختلط مدل گردیده است. سپس با توجه به محدودیت حل مسئله بصورت دقیق با استفاده از این مدل، روش برش سطحی به منظور ایجاد نامعادلاتی که برای مساله معتبرند در قالب الگوریتم شاخه و برش پیشنهاد گردیده است. هدف از اضافه کردن این مجموعه‌ از نامعادلات، ایجاد کران پایینی است که در عین حال که جواب‌های شدنی توسط آنها حذف نمی‌شود، باعث تسریع حل در قالب الگوریتم شاخه و برش می‌شود. برای حل مساله به صورت بهینه، نتایج نشان می‌دهد که حدود پایین ایجاد شده توسط مدل مجددا فرموله شده، قوی تر از حدود پایین ایجاد شده توسط مدل اصلی آزاد شده می‌باشد.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

Branch & cut algorithm for solving the job shop scheduling problem using valid inequalities

نویسندگان [English]

  • Javad Behnamian 1
  • Fatemeh Komijani 2
1 Department of Industrial Engineering, Bu-Ali Sina University
2 Industrial Engineering Department, Bu-Ali Sina University
چکیده [English]

In this paper, the problem of scheduling the job shop production is considered, which, while being applicable as one of the complex issues in the field of combinatorial optimization, has been raised and this has caused the researchers to pay more attention to this problem. In this problem, given the existence of a number of workshops, the number of jobs should be processed in the workshop with a known production path that is already known. In order to solve this problem, in this paper, the problem of production scheduling is firstly modeled as a mixed integer programming. Then, due to the limitations of the exact solving using this model, the surface cutting method is proposed to create inequalities this is valid for the problem in the framework of branching and cutting algorithm. The aim of adding this set of inequalities is to create a lower bound, which, while the feasible solutions are not eliminated by them, accelerates the solution in the framework of branch & cut algorithm. To solve the problem optimally, the results show that the lower bound created by the re-formulated model is stronger than the lower bound created by the original relaxed model.

کلیدواژه‌ها [English]

  • Scheduling
  • Job shop problem
  • Branch and cut
  • Valid inequalities
[1]    Muth J.F., Thompson G.L. (1963). “Industrial scheduling”, Thompson, Gerald Luther, Englewood Cliffs, N.J., Prentice-Hall.
[2]    Carlier, J., Pinson, E., (1989). “An Algorithm for Solving the Job-Shop Problem”, Management Science, 35(2): 164-176.
[3]    Ashour, S., Hiremath, S.R., (1973). “A branch-and-bound approach to the job-shop scheduling problem”, International Journal of Production Research, 11(1): 47-58.
[4]    Kharbeche, M., Mohamed. H., (2013). “MIP models for minimizing total tardiness in a two-machine flow shop”, Journal of the Operational Research Society, 64(5): 690-707.
[5]    Zhang, M., Simge, K., Hande, Y., (2012). “A polyhedral study of multiechelon lot sizing with intermediate demands”, Operations Research, 60(4): 918-935.
[6]    Kianfar, K., (2012). “On n-step MIR and partition inequalities for integer knapsack and single-node capacitated flow sets, Discrete Applied Mathematics, 160(10): 1567-1582.
[7]    Della, C.F, Salassa, F., T'kindt, V., (2014). “A hybrid heuristic approach for single machine scheduling with release times”, Computers & Operations Research, 45: 7-11.
[8]    Pessan, C., Emmanuel, N., Mohamed, H., (2013). “Development of lower bounds for the scheduling of setup tasks in serial production lines”, European Journal of Industrial Engineering 7, 5: 558-576.
[9]    Gicquel, C., Michel, M., (2015). “Multi-product valid inequalities for the discrete lot-sizing and scheduling problem”, Computers & Operations Research, 54: 12-20.
[10] Behdani, B., Cole, J.S., (2014). “An integer-programming-based approach to the close-enough traveling salesman problem”, INFORMS Journal on Computing, 26(3): 415-432.
[11] Louveaux, F.V., Salazar-González, J.J., (2014). “Solving the Single Vehicle Routing Problem with Variable Capacity”, Transportation Science, 50(2): 708-719.
[12] Esmaeilbeigi, R., Charkhgard, P., Charkhgard, H., (2016). “Order acceptance and scheduling problems in two-machine flow shops: New mixed integer programming formulations”, European Journal of Operational Research, 251(2): 419-431.
[13] Subramanyam, A., Chrysanthos, E.G., (2016). “A branch-and-cut framework for the consistent traveling salesman problem”, European Journal of Operational Research, 248(2): 384-395.
[14] Sundar, K., Sivakumar, R., (2016). “Generalized multiple depot traveling salesmen problem—Polyhedral study and exact algorithm”, Computers & Operations Research, 70: 39-55.
[17] S., Silvestri, Laporte, G., Cerulli, R. (2017). “A branch-and-cut algorithm for the minimum branch vertices spanning tree problem”, Computers & Operations Research, 81: 322-332.
[20] Fernandes, S., Helena R.L. (2008). “Optimised search heuristic combining valid inequalities and tabu search”, International Workshop on Hybrid Metaheuristics, Springer Berlin Heidelberg.
[21] Karimi-Nasab, M., Seyedhoseini, S.M., (2013). “Multi-level lot sizing and job shop scheduling with compressible process times: A cutting plane approach”, European Journal of Operational Research, 231(3): 598-616.
[22] Benziani, Y., Kacem, I., Laroche, P., (2013). “Lower and upper bounds for the Job Shop Scheduling problem with min-sum criteria. Control”, Decision and Information Technologies (CoDIT), 2013 International Conference on. IEEE.
[23] Karimi-Nasab, M., Modarres, M., (2015). “Lot sizing and job shop scheduling with compressible process times: A cut and branch approach”, Computers & Industrial Engineering, 85: 196-205.
[24] Ham, A.M., Eray, C., (2016). “Flexible job shop scheduling problem with parallel batch processing machines: MIP and CP approaches”, Computers & Industrial Engineering, 102: 160-165.
[25] Barker, J.R., (1981). “Primal search tree algorithms for the general job shop problem”.
[26] Balas, E., (1969). “Machine sequencing via disjunctive graphs: an implicit enumeration algorithm”, Operations research, 17(6): 941-957.
[27] Balas, E., (1979). “Disjunctive programming”, Annals of Discrete Mathematics, 5: 3-51.
[28] Balas, E., (1985). “On the facial structure of scheduling polyhedra, Springer Berlin Heidelberg, 24: 179-218.
[29] Gokce, E.I., Wilbert, E.W., (2015). “Valid inequalities for the multi-dimensional multiple-choice 0–1 knapsack problem”, Discrete Optimization, 17: 25-54.
[30] Laurence, A., (1998). Wolsey, Integer Programming, Wiley.