Comparing Mixed-Integer and Constraint Programming for the No-Wait Flow Shop Problem with Due Date Constraints

Document Type : Research Paper

Authors

1 Department of Finance and Management Science, Edwards School of Business, University of Saskatchewan, Saskatoon, Saskatchewan, Canada, S7N 5A7

2 Department of Industrial Engineering University of Sistan and Baluchestan Zahedan, Iran

Abstract

The impetus for this research was examining a flow shop problem in which tasks were expected to be successively carried out with no time interval (i.e., no wait time) between them. For this reason, they should be completed by specific dates or deadlines. In this regard, the efficiency of the models was evaluated based on makespan. To solve the NP-Hard problem, we developed two mathematical models. Once we solved our problem using Mixed-Integer Programming Model (henceforth MIPM) and then, we applied a Constraint Programming Model (CPM); finally, we compared the optimality of the presented results.

Keywords

References

Afshar-Nadjafi, B. (2014). A solution procedure for preemptive multi-mode project scheduling problem with mode changeability to resumption. Applied Computing and Informatics, DOI: 10.1016/j.aci.2014.02.003.
Beasley, J. E. (1990). OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11), 1069-1072.
Błażewicz, J., Pesch, E., Sterna, M., & Werner, F. (2005). The two-machine flow-shop problem with weighted late work criterion and common due date. European Journal of Operational Research, 165(2), 408-415.
Błażewicz, J., Pesch, E., Sterna, M., & Werner, F. (2008). Metaheuristic approaches for the two-machine flow-shop problem with weighted late work criterion and common due date. Computers & Operations Research, 35(2), 574-599.
Brah, S. (1996). A comparative analysis of due date based job sequencing rules in a flow shop with multiple processors. Production Planning & Control, 7(4), 362-373.
Carlier, J. (1978). Ordonnancements a contraintes disjonctives. RAIRO Recherche Operationnelle, 12, 333-351.
Dhingra, A. & Chandna, P. (2010). Hybrid genetic algorithm for SDST flow shop scheduling with due dates: a case study. International Journal of Advanced Operations Management, 2(3), 141-161.
Ebrahimi, M., Fatemi Ghomi, S., & Karimi, B. (2013). Hybrid flow shop scheduling with sequence dependent family setup time and uncertain due dates. Applied Mathematical Modelling.
Garcia, C. (2016). Resource-constrained scheduling with hard due windows and rejection penalties. Engineering optimization, 48(9), 1515-1528.
Gowrishankar, K., Rajendran, C., & Srinivasan, G. (2001). Flow shop scheduling algorithms for minimizing the completion time variance and the sum of squares of completion time deviations from a common due date. European Journal of Operational Research, 132(3), 643-665.
Grabowski, J. & Pempera, J. (2000). Sequencing of jobs in some production systems. European Journal of Operational Research, 125, 535-550.
Gupta, J. N., Lauff, V., & Werner, F. (2000). On the solution of 2-machine flow shop problems with a common due date. Operations Research Proceedings 1999, Springer.
Hall, N. & Sriskandarajah, C. (1996). A survey of machine scheduling problems with blocking and no-wait in process. Operations Research, 44, 510-525.
Hasanzadeh, A., Afshari, H., Kianfar, K., eFathi, M., & Jadid, A. O. (2009). A GRASP algorithm for the two-machine flow-shop problem with weighted late work criterion and common due date. IEEE International Conference on Industrial Engineering and Engineering Management.
Hunsucker, J. & Shah, J. (1992). Performance of Priority Rules in a Due Date Flow Shop. Omega, 20(1), 73-89.
Javadi, B., Saidi-Mehrabad, M., Haji, A., Mahdavi, I., Jolai, F., & Mahdavi-Amiri, N. (2008). No-wait flow shop scheduling using fuzzy multi-objective linear programming. Journal of the Franklin Institute, 345(5), 452-467.
Kaminsky, P. & Lee, Z. H. (2002). On-line algorithms for flow shop due date quotation. University of California, Berkeley (California, USA). http://www.ieor.berkeley.edu/~kaminsky/papers/ddq_flowshop.pdf.
Pan, C. H. (1997). A study of integer programming formulations for scheduling problems. International Journal of Systems Science, 28(1), 33-41.
Pan, J. C. H., & Chen, J. S. (2005). Mixed binary integer programming formulations for the reentrant job shop scheduling problem. Computers & Operations Research, 32(5), 1197-1212.
Panwalkar, S. & Koulamas, C. (2012). An O(n^2) algorithm for the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines. European Journal of Operational Research, 221(1), 7-13.
Raaymakers, W. & Hoogeveen, J. (2000). Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing. European Journal of Operational Research, 126, 131-151.
Rajasekera, J., Murr, M., & So, K. (1991). A due-date assignment model for a flow shop with application in a lightguide cable shop. Journal of Manufacturing Systems, 10(1), 1-7.
Ramezanian, R., Aryanezhad, M., & Heydari, M. (2010). A Mathematical Programming Model for Flow Shop Scheduling Problems for Considering Just in Time Production. International Journal of Industrial Engineering, 21(2).
Samarghandi, H. & ElMekkawy, T. Y. (2012). A meta-heuristic approach for solving the no-wait flow-shop problem. International Journal of Production Research, 50(24), 7313-7326.
Sarper, H. (1995). Minimizing the sum of absolute deviations about a common due date for the two-machine flow shop problem. Applied Mathematical Modelling, 19(3), 153-161.
Selen, W. J., & Hott, D. D. (1986). A mixed-integer goal-programming formulation of the standard flow-shop scheduling problem. Journal of the Operational Research Society, 1121-1128.
Stafford, E. F. (1988). On the development of a mixed-integer linear programming model for the flowshop sequencing problem. Journal of the Operational Research Society, 1163-1174.
Tang, H. B., Ye, C. M., & Jiang, L. F. (2011). A New Hybrid Particle Swarm Optimization for Solving Flow Shop Scheduling Problem with Fuzzy Due Date. Advanced Materials Research, 189, 2746-2753.
Tari, F. G., & Olfat, L. (2013). Heuristic rules for tardiness problem in flow shop with intermediate due dates. The International Journal of Advanced Manufacturing Technology, 1-13.
Tseng, F. T., Stafford Jr., E. F., & Gupta, J. N. (2004). An empirical analysis of integer programming formulations for the permutation flowshop. Omega, 32(4), 285-293.
Wagner, H. M. (1959). An integer linear‐programming model for machine scheduling. Naval Research Logistics Quarterly, 6(2), 131-140.
Wismer, D. (1972). Solution of the flowshop scheduling with no intermediate queues. Operations Research, 20, 689-697.
Ziaee, M., & Sadjadi, S. J. (2007). Mixed binary integer programming formulations for the flow shop scheduling problems. A case study: ISD projects scheduling. Applied Mathematics and Computation, 185(1), 218-228.
Journal of Quality Engineering and Production Optimization
Volume 4, Issue 1
June 2019
Pages 17-24

Files

Share

How to cite

Statistics