A new MIP approach for balancing and scheduling of mixed model assembly lines with alternative precedence relations

ABSTRACT

In this paper, a new mixed integer programming (MIP) formulation is developed for balancing and scheduling of mixed model assembly lines with disjunctive precedence constraints among assembly tasks. To represent alternative precedence relations, AND/OR assembly graph was adopted. In case of alternative precedence relations, for each product multiple assembly plans exist, which can be represented by a set of alternative precedence subgraphs and only one of such subgraphs should be selected for each product. As the number of subgraphs exponentially increases with the number of disjunctive relations among the tasks, the computational complexity of simultaneous balancing and scheduling along with the assembly subgraph selection increases with the number of alternative precedence relations. Unlike the other MIP approaches known from the literature, the new model does not need the alternative assembly subgraphs to be to explicitly enumerated as input data and then used for indexing the variables. Instead, a new disjunctive precedence selection and task assignment variable and new constraints are introduced to optimally choose one relation for each subset of alternative precedence relations. The optimal solutions for computational examples of balancing and scheduling problems illustrate a superior performance of the new modelling approach.

KEYWORDS:

• Mixed-model assembly line
• balancing and scheduling
• alternative precedence relations
• mixed integer programming

Acknowledgments

The author acknowledges the helpful comments and improvement suggestions by three anonymous reviewers.

Data availability statement

The data that support the findings of this study are available from the corresponding author, upon reasonable request.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Tadeusz Sawik

Tadeusz Sawik is a professor of industrial engineering and operations research in the Department of Engineering, Reykjavik University in Reykjavik, Iceland, and at AGH University of Science and Technology in Kraków, Poland. He received the MS degree in automation engineering, the PhD degree in operations engineering and the Habilitation degree in operations research, all from AGH University. He has been a visiting professor in France, Germany, Greece, Japan, Portugal, Spain, Sweden and Switzerland and has served as a research advisor of Motorola for several years. He is a sole author of numerous books, including Analysis and Synthesis of Multivariable Control Systems, AGH University Press 1984, Discrete Optimisation in Flexible Manufacturing Systems, WNT Publishers 1992, Operations Research for Industrial Engineers, AGH University Press 1998, Production Planning and Scheduling in Flexible Assembly Systems, Springer 1998, Scheduling in Supply Chains Using Mixed Integer Programming, Wiley 2011 and Supply Chain Disruption Management Using Stochastic Mixed Integer Programming, Springer 1st edition 2018, 2nd edition 2020, and more than 150 individual articles in many prestigious journals. He has been a recipient of various individual awards for research achievements, including five times of Scientific Excellence Award from the Minister of Science and Higher Education and over 25 times of Scientific Award from the Rector of AGH. In the World's Top 2% Scientists list recently released by Stanford University and published in PLoS Biology, ranked #144 in Operations Research until the end of 2021, and #71 during the single calendar year 2021. His current research interests include logistics and supply chain management, supply chain risk management, cyber and homeland security, planning and scheduling, mixed integer programming, stochastic and combinatorial optimisation.