A computational study of the influence of the parameter big-M in a time-indexed MILP for assembly flowshop

Authors

Keywords:

Mixed Integer Linear Programming, Scheduling, Assembly Flowshop, big-M influence

Abstract

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.

Downloads

Download data is not yet available.

Author Biographies

José Renatho da Silva Santana, Universidade Federal de Goiás - UFG

Production Engineer graduated from the Pontifical Catholic University of Goiás. Student in the Master's Program in Production Engineering at the Faculty of Science and Technology (FCT) at UFG. Works as a researcher in the field of Production Sequencing (Scheduling). Has knowledge in project management with a focus on Agile Methodologies. He currently works as a project manager in a consulting and advisory company for companies with e-commerce. Developed research and extension project in a food industry with a focus on reducing costs and waste, as well as having experience in developing projects focused on Lean Manufacturing and people management in the application of agile routines focused on strategic and operational results in companies of different segments.

Hélio Yochihiro Fuchigami, Universidade Federal de Goiás - UFG

Professor and researcher at the Federal University of Goiás (UFG). Coordinator of the Master's Degree in Production Engineering at the Faculty of Science and Technology (FCT) at UFG. Professor at the Production Engineering course at Campus Aparecida de Goiânia and at the Master's in Public Administration Network (PROFIAP). Works in the Production Sequencing (Scheduling) and Operational Research area. Computer Scientist at UNESP, Master and Doctor in Production Engineering at USP, with part of his doctorate at the Polytechnic University of Valencia, Spain. Post-doctorate at the University of New South Wales (Australian Defense Force Academy) in Australia and at UNESP/São José do Rio Preto. Master's advisor, specialization, scientific and technological initiation, course conclusion work and internship. Chronicler and poet, with three published books.

References

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.

Downloads

Published

2022-01-13

How to Cite

da Silva Santana, J. R., & Yochihiro Fuchigami, H. (2022). A computational study of the influence of the parameter big-M in a time-indexed MILP for assembly flowshop. IEEE Latin America Transactions, 20(5), 848–854. Retrieved from https://latamt.ieeer9.org/index.php/transactions/article/view/6142

Issue

Vol. 20 No. 5 (2022): Ordinary Issue

Section

Articles