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

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, Bu-Ali Sina University

2 Industrial Engineering Department, Bu-Ali Sina University

Abstract

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.

Keywords

Main Subjects

References

[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.
[15] Györgyi, P., Kis, T., (2018). “Minimizing the maximum lateness on a single machine with raw material constraints by branch-and-cut”, Computers & Industrial Engineering, 115: 220-225.
[16] Hoffmann, K., Buscher, U., (2018). “Valid inequalities for the arc flow formulation of the railway crew scheduling problem with attendance rates”, Computers & Industrial Engineering, In press.
[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.
[18] Dalmeijer, K., Spliet, R., (2018). “A branch-and-cut algorithm for the Time Window Assignment Vehicle Routing Problem”, Computers & Operations Research, 89: 140-152.
[19] Lefever, W., Aghezzaf, E.H., Bernard Penz, K.H.H., (2018). “Analysis of an improved branch-and-cut formulation for the Inventory-Routing Problem with Transshipment”, Computers & Operations Research, 98: 137-148.
[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.
Journal of Industrial Engineering Research in Production Systems
Volume 6, Issue 13
Winter and Spring 2019
March 2019
Pages 139-149

Files

Share

How to cite

Statistics