A computational study of the influence of the parameter big-M in a time-indexed MILP for assembly flowshop
Keywords:Mixed Integer Linear Programming, Scheduling, Assembly Flowshop, big-M influence
In this paper, a mixed integer linear programming model was proposed to solve the assembly flowshop scheduling problem. The objective of the study was to evaluate the impact on computational time (CPU) from the variation of the value of the big-M parameter considering three different dimensions. The performance of the mathematical model was evaluated from the application of a commercial solver that has different strategies in search of the optimal solution. 240 test-problems were solved on the optimality in an acceptable computational time, with the number of jobs ranging from 4 to 8, the number of products from 2 to 4 and the number of machines from 1 to 4. The performance profiles of Dolan and More (2002) were employed for a more accurate statistical analysis of the results, which indicated the most efficient value for the big-M parameter in the proposed mathematical formulation.
Morton, Thomas E.; Smunt, Timothy L. A planning and scheduling system for flexible manufacturing. In: Flexible Manufacturing Systems: Methods and Studies. North-Holland, 1986. p. 151-164.
A.S. Kiran and S. Alptekin, Scheduling algorithms for flexible manufacturing system. Dept. of Industrial and Systems Engineering, University of Southern California, Los Angeles. n. 85, 1985.
Ríos-Mercado, Roger Z.; Ríos-Sólis, Yasmín A. Just-in-Time Systems. New York: Springer Optimization And Its Application, 2012.
Józefowska, J. Just-in-Time Scheduling: Models and Algorithms for Computer and Manufacturing Systems. Springer, International Series in Operations Research & Management Science, 2007.
Kusiak A. Aggregate scheduling of a flexible machining and Assembly system. IEEE Trans Robotics Automat, 1989.
He, D.; Babayan and A; Kusiak A. Scheduling manufacturing systems in an agile Environment. Robotics and Computer Integrated Manufacturing, v 17. p. 2461-2481, 2001.
Wagner HM. An integer linear-programming model for machine scheduling. Naval Research Logistics Quarterly, v. 6, p. 131–140, 1959.
Manne As. On the job shop scheduling problem. Cowles Foundation Discussion. Cowles Foundation for Research in Economics, Yale University, v. 73, 1959.
J.P. Sousa, Time indexed formulations of non-preemptive single-machine scheduling problems. Ph.D. Thesis, Faculté des Sciences Appliquées, Université Catholique de Louvain (Louvain-la-Neuve, Belgium), 1989.
Dyer Me and Wolsey LA. Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Appl. Math., v. 26, p. 255–270, 1990.
Sousa JP and Wolsey LA. A time indexed formulation of non-preemptive single machine scheduling problems. Mathematical Programming, v. 54, p. 353–367, 1992.
Crama, Y., Spieksma, Scheduling jobs of equal length: complexity, facets and computational result. Mathematical Programming v. 72, p. 207–227, 1996.
Avella P, Boccia, M. and D’auria, B. Near-optimal solutions of large-scale single-machine scheduling problems. Informs Journal on Computing, v. 17, p. 183–191, 2005.
Bigras L-P, Gamache M and Savard G. The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times. Discrete Optimization, v. 5, p. 685–699, 2008.
Keha AB, Khowala K and Fowler JW. Mixed integer programming formulations for single machine scheduling problems. Computers & Industrial Engineering, v. 56, p. 357-367, 2009.
WU, Shuang; REN, Xiaoqiang; DEY, Subhrakanti; SHI, Ling. Optimal Scheduling of Multiple Sensors with Packet Length Constraint, v. 50, n. 1, p. 14430-14435, 2017.
Unlu, Y. and Mason SJ. Evaluation of mixed integer programming formulations for nonpreemptive parallel machine scheduling problems. Computers & Industrial Engineering, v. 58, p. 785–800, 2010.
M. Garraffa, L. Shang, F. Della Croce, V. T’kindt. An exact exponential branch-and-merge algorithm for the single machine total tardiness problem, Theoretical Computer Science, v. 745, p. 133-149, 2018.
Potts, C. N., Sevast'Janov, S. V., and Zwaneveld, C. M. The two-stage Assembly scheduling problem: complexity and approximation. Operations Research, v. 43, p. 346-355, 1995.
Koulamas, C., and G. J. Kyparisis. The Three-Stage Assembly Flowshop Scheduling Problem. Computers and Operations Research, v. 28, p. 689–704, 2001.
Zhang, Y., Z. Zhou, and J. Liu. The Production Scheduling Problem in a Multi-Page Invoice Printing System. Computers and Operations Research, v. 37, p. 1814–1821, 2010.
Deng, J., L. Wang, S. Y. Wang, and X. L. Zheng. A Competitive Memetic Algorithm for the Distributed two-Stage Assembly Flow-Shop Scheduling Problem. International Journal of Production Research v. 54, p. 3561–3577, 2016.
Sheikh, Shaya; Komaki, G.M.; Kayvanfar, Vahid; Teymourian, Ehsan. Multi-Stage Assembly Flowshop with setup time and release time. Operations Research Perspectives, v. 6, p. 100-111, 2019.
Terekhov, D., M. K. Dogru, U. Özen, and J. C. Beck. Solving Two-Machine Assembly Scheduling Problems with Inventory Constraints. Computers & Industrial Engineering, v. 63, p. 120–134, 2012.
Yavari, Mohammad; Isvandi, Sahar. Integrated decision making for parts ordering and scheduling of jobs on two-stage Assembly problem in three level supply chain. Journal of Manufacturing Systems, v. 46, p. 137-151, 2018.
Yavari, Mohammad; Marvi, Mohammad; Akbari, A. Hosein. Semi-permutation-based genetic algorithm for order acceptance and scheduling in two-stage Assembly problem. Neural Computing and Applications, v. 32, p. 2989–3003, 2019.
Dolan, Elizabeth D.; Moré and Jorge J. Benchmarking optimization software with performance profiles. Mathematical Programming, Springer Science and Business Media LLC. v. 91, n. 2, p. 201-213, 2002.