مدل سازی و حل مسئله متعادل کردن خط مونتاژ مدل مخلوط با نصب و راه اندازی؛ قسمت اول: یک مدل برنامه ریزی خطی عدد صحیح مختلط

This paper is the first one of the two papers entitled “modeling and solving mixed-model assembly line balancing problem with setups”, which has the aim of developing the mathematical programming formulation of the problem and solving it with a hybrid meta-heuristic approach. In this current part, a mixed-integer linear mathematical programming (MILP) model for mixed-model assembly line balancing problem with setups is developed. The proposed MILP model considers some particular features of the real world problems such as parallel workstations, zoning constraints, and sequence dependent setup times between tasks, which is an actual framework in assembly line balancing problems. The main endeavor of Part-I is to formulate the sequence dependent setup times between tasks in type-I mixed-model assembly line balancing problem. The proposed model considers the setups between the tasks of the same model and the setups because of the model switches in any workstation. The capability of our MILP is tested through a set of computational experiments. Part-II tackles the problem with a multiple colony hybrid bees algorithm. A set of computational experiments is also carried out for the proposed approach in Part-II.

In 1913, Henry Ford changed the type of manufacturing system by introducing a moving belt in a factory for the first time. Before the moving belt, workers were able to build one piece of an item at a time instead of an item at a time. This changed type of manufacturing system named as assembly line and reduced the cost of production. Over the years a new problem type, design of efficient assembly lines, increased in importance. Assembly line balancing problem (ALBP) is a well-known assembly design problem, which consist of partitioning the assembly work among the workstations so as to optimize some objective. Assembly lines were firstly created to produce one single homogeneous product in high volumes. The balancing problem of this type of lines named as simple assembly balancing problem (SALBP), which was first mathematically formulated by Salveson [1]. Single-model assembly lines are the least suited production system for high variety demand scenarios. Current consumer-centric market conditions require high flexibility in manufacturing systems. Hence, assembly lines must be designed so as to satisfy high-mix/low volume manufacturing strategies. Due to high cost to build and maintain an assembly line, the manufacturers produce one model with different features or several models on a single assembly line. This changed type of assembly lines lead to arise the mixed-model assembly line balancing problem, which was handled by Thomopoulos for the first time in the literature [2]. The relevant literature about the solution procedures of the mixed-model assembly lines was initiated by the approaches of Thomopoulos [3] and can be divided into three groups: mathematical programming, heuristics and meta-heuristics, and hybrid approaches. For more detailed information, the reader can refer to Battaïa and Dolgui for a recent survey [4]. Heuristic and meta-heuristic approaches were widely used in order to cope with the problem. The field of hybrid approaches has become very popular among researchers because of the insufficient performance of heuristics and pure meta-heuristics while exploring the solution space effectively as problems get larger and more complex as in the real life. On the other hand, mathematical programming approaches are used to formally describe the problem. In this paper we proposed a new mathematical programming model for type-I mixed-model assembly line balancing with sequence dependent setup times between tasks (MMALBPS-I). To the best of our knowledge, this is the second attempt to model type-I mixed-model assembly line balancing problem while considering the sequence dependent setup times in the literature. The first attempt belongs to Nazarian et al. [5] and a comparison between these two models will be given in Section 3. Akpinar et al. summarized the published papers related to type-I mixed-model assembly line balancing problem (MMALBP-I) between the years 1997 and 2011 by taking into account the line configuration, the methodology, and the employed data to test the performance of the proposed approach [6]. From their summary, it is observed that few papers dealt with mathematically modeling of the MMALBP-I and none of these studies handled the sequence dependent setup times between tasks except Nazarian et al.’s study [5]. Askin and Zhou proposed a non-linear integer mathematical model for MMALBP-I [7]. Their model allows using parallel workstations if required. By the way, the authors relaxed the splitting restriction for the first time. Gokcen and Erel modeled the MMALBP-I as a binary goal program [8]. They considered several conflicting goals and their model provides flexibility to the decision maker. Their model also allow to the use of zoning constraints. Moreover, Gokcen and Erel developed a binary integer programming model for the MMALBP-I [9]. The authors stated that their model may be used as a validation tool for the heuristic procedures for the MMALBP-I. On the hand, Erel and Gokcen proposed a shortest-route formulation of the MMALBP-I [10]. Vilarinho and Simaria combined the concepts of parallel workstations assignment and zoning constraints in their mathematical programming model [11]. Their model aims at minimizing the number of workstations as a primary goal, and balancing the workloads between and within workstations as a secondary goal. The literature about the mixed-model assembly line balancing problem (MMALBP) use a restriction ensures that assigning common tasks of different models to the same workstation. This restriction has been relaxed by Bukchin et al. [12], and Bukchin and Rabinowitch [13] and they allow the assignment of a common task for multiple products to different workstations. The same relaxation was also used by Kara et al. [14]. They proposed a new binary mathematical programming model based on the Bukchin and Rabinowitch's [13] model and have also developed two goal programming approaches, one with precise and the other with fuzzy goals. Hop dealt also with fuzzy concept and handled the MMALBP with fuzzy processing times and formulated the problem as a fuzzy binary linear programming model, which was transformed to a mixed zero-one program [15]. Simaria and Vilarinho dealt with the MMALBP-I with a different line configuration, two-sided assembly line and developed a mathematical programming model covers the parallel workstations assignment and zoning constraints [16]. The phenomenon of two-sided assembly lines was also handled by Özcan and Toklu [17]. They also proposed a mathematical programming model for the two-sided MMALBP-I. On the other hand, Sparling and Miltenburg [18], and Kazemi et al. [19] handled the U-line MMALBP-I. They all developed mathematical programming models for the problem. In this paper, we deal with the MMALBP-I with some particular features of the real world problems such as parallel workstations and zoning constraints. Furthermore, we extend the problem by adding sequence dependent setup times between tasks, which is a new concept for assembly line balancing problem. We developed a mixed integer linear programming (MILP) model for formally describing the extended problem. The rest of the paper is organized as follows. In Section 2, an overview on the concept of sequence-dependent setup times in assembly line balancing are given. The proposed MILP model is given in Section 3. An illustrative example is solved in Section 4. Computational experiments are given in Section 5. Finally, the discussions and conclusions are presented in Section 6.

In this paper we aimed to develop a mixed-integer linear programming model for type-I mixed-model assembly line balancing problem enriched with the sequence dependent setup times between the tasks. The MILP provides us the formal formulation of MMALBPS-I. Moreover, our MILP model can solve the problem with and without sequence dependent setup times, parallel workstation assignments, and zoning constraints. Since, the SALBP-I is a special case of MMALBP-I, our MILP is also able to solve SALBP-I with and without the aforementioned characteristics. Thus, we can conclude that our MILP is a general model for some of the assembly line balancing problems. In future research, we might extend the proposed MILP so as to solve assembly line balancing problems with different line configurations.