Developing a bi-objective schedule for an online cellular manufacturing system in an MTO environment

Abstract

So far, a great bulk of research has been dedicated to demand fluctuations in the make-to-order (MTO) environment, and several solutions have been proposed. In contrast, cellular layouts have received little attention from researchers. Also, in studies on dynamic cell production systems, the concept of dynamics is limited to the possibility of making changes between periods. This paper presents a new mathematical model to create an integrated system of order prioritizing, capacity measurement, and scheduling for dealing with new orders in MTO environments arranged by a cellular manufacturing layout. In this model, it is possible to negotiate the price and delivery time. The periods are also considered to be connected, and unlike the existing dynamic cellular manufacturing systems (DCMSs), it is possible to receive an order at any moment. Moreover, machine relocation is allowed with regard to the time of relocation during the periods. Another notable feature is the alternative routing for parts and cell formation (CF) at the same time as scheduling. The proposed model has two objectives including a) maximizing the profit and b) maximizing the number of orders accepted based on their priorities. The bi-objective model for small sizes has been solved by GAMS software using the augmented epsilon-constraint method. The effects of key parameters as well as some important features of the model, such as the possibility of checking the acceptance/rejection of a new order during the program, are addressed. Generally, the proposed model is able to develop a DCMS in an online cellular manufacturing system (OCMS). The results of sensitivity analysis show that the integration of CF, GS, order acceptance, pricing, and delivery time in a mathematical model simultaneously can significantly improve system performance and increase system profits. Finally, an NSGA-II algorithm is developed to solve the problem in larger sizes. To verify the computational effectiveness of the employed NSGA-II in comparison with a CPLEX solver, its performance is evaluated using two methods.

1 Introduction

MTO is one of the policies adopted by some manufacturing companies that make their products based on the customer demand. These companies may also use make to stock (MTS), engineering to order (ETO), assembly to order (ATO), or a combination of them to meet customer demands. Each of these policies has its advantages and disadvantages. The advantages of MTO include low inventory cost, high flexibility in responding to customer orders, and low risk in selling products.

As markets become more competitive and companies increasingly move toward the MTO approach, businesses need to cope with the changes in demand better than before if they are to effectively decide whether to reject or accept an order. This order can be one of the products available in the factory or a new product. There have been many studies conducted on accepting or rejecting a new order in a manufacturing system with the MTO policy. A considerable part of that research has been on the use of a multi-level system to reject or accept new orders, which often includes steps such as capacity measurement, order prioritization, determination of delivery time and pricing, and order scheduling (Hemmati et al. 2012; Ebadian et al. 2008, 2009; Manavizadeh et al. 2013; Kalantari et al. 2011; Rabbani et al. 2017). A review of the literature shows that two points have been sufficiently dealt with. First, in most studies, the layout is job shop, flow shop or a combination of them, and the cellular layout has been ignored despite the features that bring the system closer to the nature of the MTO environment. Second, the proposed mathematical models often do not take into account all the steps mentioned to reject or accept a new order. Most of them cover part of these steps or are presented as separate mathematical models for individual steps, which may lead to non-optimal solutions. In this paper, however, a mathematical model is presented to integrate the mentioned steps in an MTO environment under a cellular manufacturing system. The model not only makes it possible to decide whether to reject or accept new orders but also allows their prioritization, pricing, determination of delivery time, capacity measurement, and scheduling of orders. The effect of accepting an order on the delivery time of the existing orders is also shown with this model.

Models for DCMSs discussed in this paper were first introduced by Rehalat et al. (1995). In these models, it is assumed that changes in the composition and the quantity of the products in demand can be predicted, so multi-period planning is possible. Indeed, a planning horizon can be divided into smaller periods, each with its product mix and demand. Therefore, under dynamic conditions, a cell structure in one period may not be optimal for the next. So far, many researchers have addressed the cellular manufacturing systems problem using mathematical models. Their models all have the same general structure but do not take into account the possibility of entering an order at any moment. They also assume that orders are received as expected and only at the beginning of time periods. This is while an order may be offered to the system for many times during a period. After the order is offered, the production unit must decide whether to reject or accept it according to such criteria as price, capacity, delivery time, and the effect of accepting the new order on the schedule of the other orders. Also, to accept a new order, the system may require changes that must be made before the end of the period. Therefore, the scheduling part of the model takes the possibility of machine relocation during a period into consideration. Moreover, considering the connected periods, orders can be logged in at any time. The objectives are to maximize the number of the accepted orders and minimize the earliness and tardiness penalties as well as the other corresponding costs. The innovations of this study can be summarized in the following items:

Compared to the scheduling models existing in CMSs	The literature was reviewed, but there was no mathematical model for simultaneous scheduling, CF, alternative processing routes, and periods
	The model presented in this paper is the first one to consider the time of machine relocation and the possibility of relocation during a period, which enables the system to have shorter interruptions to make changes from one period to another
	Considering the connected periods, there is no need to match the entry of the demands with the beginning of the periods
Compared to the models in the MTO environment	This study presents the basic steps of accepting or rejecting a new order (including prioritization, capacity measurement, pricing, and timing of delivery and scheduling) in an integrated mathematical model
	CMSs have not been studied in this field so far

This paper consists of six main sections. After this section, the literature will be reviewed for manufacturing systems in the MTO environment and scheduling in CMSs. In the third section, a nonlinear mixed-integer programming mathematical model is presented and linearized. The fourth section presents the designed NSGA-II algorithm. In the fifth section, a numerical example is solved by a CPLEX solver and a number of problems are solved to explore the model features, analyze its sensitivity and show the NSGA-II algorithm performance. Finally, the paper is closed up with the conclusion of the study.

2 Literature review

A review of the literature in the field is presented here in two sections including MTO environment and scheduling in CMSs.

2.1 MTO environment

Sawik (2006) proposed a hierarchical method of scheduling in an MTO environment. They also developed an integer programming model to schedule production in a hybrid flow shop system. Piya (2019) designed a mathematical model to help manufacturer and customers revise their offers in negotiations. In the same line of research, Piya et al. (2016) assist manufacturers in the MTO environment by providing a mathematical model to decide whether to reject or accept orders. In this case, different processes are used, and the contingency of the orders is taken into account. Choy et al. (2011) presented a mathematical model to minimize tardiness, addressing the problem of scheduling in an MTO production environment. They used a genetic algorithm (GA) and an optimization module to solve their proposed model. Garmadre et al. (2018) developed a nonlinear mixed-integer mathematical model for integrated pricing, delivery date determination, and new order scheduling. The objective of the model is to maximize profit by considering regular time, overtime and subcontracting operational costs, raw material costs, resource unemployment costs as well as tardiness and earliness costs. Zaharie et al. (2017) proposed a bi-objective integer programming mathematical model to accept or reject orders, determine the delivery date, and schedule orders in an apparel manufacturing company. The first goal of the model is to maximize the number of orders delivered to the customer on time, and the second goal is to minimize the maximum delay in the delivery of the orders. Wang et al. (2019a) presented an integrated mathematical model for order acceptance and order scheduling in a job shop production under the hybrid MTO/MTS production environment. In their model, MTS orders are produced under a fixed schedule, and MTO orders, if accepted, are processed during the idle time slots of the schedule of MTS tasks. Jiang et al. (2020) proposed a model for order acceptance and scheduling in a random multiple-order environment to increase profits and reduce costs in terms of tardiness and earliness. They used a GA to solve their model. Ghiyasinasab et al. (2020) presented a multi-objective production planning model for the order scheduling of engineered wood products in the construction industry. The model was put to practice in the ETO environment. For this purpose, they presented four mathematical models. Yousefnejad and Esmaeili (2018) used the Stackelberg game to investigate the problem of pricing and lead time determination in a hybrid MTS/MTO production environment. They addressed three types of products including MTS, MTO, and MTS/MTO. The intended manufacturing system consisted of a common stage and a stage of differentiation. Abdollahpour and Rezaian (2017) presented a mathematical model for scheduling problem in flow shop system under a hybrid MTS/MTO production environment. The objective of the proposed model is to minimize tardiness and earliness, as well as to minimize the number of missed and incomplete orders. Rostami et al. (2020a, b), by presenting a multi-objective mathematical model for the first time in a virtual cellular manufacturing (VCM), introduced the concept of developing a new product.

The studies conducted in the MTO environment have mainly dealt with job shop and flow shop production systems, or a combination of them. These studies have paid little attention to the CMS, despite its proximity to the nature of the MTO environment. Furthermore, the mathematical models presented in these studies address only a few aspects of accepting or rejecting new orders, and these aspects have been presented in several separate models. In this study, however, in addition to a cellular layout, decisions on capacity measurement, order acceptance, pricing, delivery time determination, and scheduling of new orders with the possibility of influencing the existing orders are integrated with a mathematical model. Table 1 makes a comparison of the model presented in this study and some mathematical models reported in the MTO environment.

Table 1 Comparison of the mathematical models presented in the MTO environment

2.2 Scheduling and CMS

Wu et al. (2007) proposed a nonlinear mathematical model to consider three decisions simultaneously, including CF, group layout (GL), and GS. The objective of this model is to minimize completion time. To solve the model, they proposed a hierarchical genetic algorithm (HGA) with a dynamic function for the selection operator. Tavakkoli-Moghaddam et al. (2008) designed a nonlinear mathematical model to investigate the problem of GS in a CMS so as to minimize completion time. To solve the problem, they proposed two evolutionary algorithms called GA and memetic algorithm (MA). Tavakkoli-Moghaddam et al. (2010) and Gholipour-Kanani et al. (2011), introduced a nonlinear mathematical model for the GS problem in CMSs. The objective of the model is to minimize intracellular material handling time, completion time, tardiness time, and sequence-dependent setup costs. To solve their model, they proposed a meta-heuristic algorithm based on scatter search (SS). Kessen et al. (2010) proposed a mathematical model for the scheduling problem in virtual manufacturing cells (VMCs). The objective of the model is to minimize the weighted makespan and the total traveling distance. They proposed a GA for large-sized problems. Mac et al. (2007) presented a nonlinear mathematical model for the scheduling problem in VCMSs. The objective of the model is to minimize the total material traveling distance. To solve their model, they used two meta-heuristic algorithms, a GA and an ant colony optimization algorithm. Aksoy and ozturk (2010) applied a two-stage approach for the scheduling problem in VCMSs. In the first stage, the simulated annealing (SA) algorithm is used to obtain the optimal scheduling, and in the second stage, the total material traveling distance is minimized by the use of a heuristic approach. Aryanezhad et al. (2011) designed a nonlinear mathematical model for the problem of scheduling with CF simultaneously. The objective of the model is to minimize completion time. They used a GA to solve the model in large sizes. Taghavi-fard et al. (2011) presented a bi-objective mathematical model for the GS problem in CMSs. The first objective is to minimize completion time, and the second is to minimize the total tardiness. To solve the model, they proposed the NSGA-II and the non-dominated rank genetic algorithm (NRGA). Solimanpur and Elmi (2011) presented an integer linear programming model for the GS problem in CMSs. To minimize completion time, this problem includes the two subproblems of intra-group scheduling and inter-group scheduling. To solve the model, a tabu search algorithm was proposed. Karthikeyan et al. (2012) investigated the scheduling problem in a CMS using the meta-heuristic SA and tabu search algorithms. Their objective is to minimize the tardiness penalty. Arkat et al. (2012a) proposed a bi-objective nonlinear mathematical model to simultaneously investigate CF and CL and the scheduling problem to minimize the total transportation cost of the parts and minimize the makespan. They used the epsilon-constraint method to solve the model in small sizes. They also proposed the multi-objective genetic algorithm (MOGA) to solve their model. In another paper, Arkat et al. (2012b) presented two mathematical models for the integrated design of CMSs. The first model integrates the cellular layout problem and the CF problem to determine the optimal configuration of the cell and the layout of machines. In the second model, using the first model's feedbacks as the input parameter, the scheduling problem is investigated to minimize the completion time of all the parts. Taghvifard (2012) studied a scheduling problem in a CMS, intending to minimize the completion time. The problem was solved using the ant colony optimization algorithm (ACO) and compared with a heuristic algorithm called SVS. Soleimanpour and Elmi (2013) aimed at a mixed-integer linear programming model to minimize the completion time for the scheduling problem in CMSs. The nested tabu search (NTS) approach was used to solve the proposed model. Eguia et al. (2013) proposed an integer linear mathematical model to simultaneously solve a CF problem and scheduling part families in a reconfigurable cellular manufacturing system (RCMS). The objective of the model is to minimize production costs including reconfiguration costs for switching from one family to another and underutilization costs. Pajoutan et al. (2014) proposed a new nonlinear mathematical model for the scheduling problem in a CMS, considering the time for material handling and alternative processing routes. Suer et al. (2014) assumed that the operation of jobs could be distributed among the cells and that each job in a family had an individual due date. To solve the problem, they used three methods including a mathematical model using the Lingo software, a heuristic algorithm, and a GA, to solve this problem. Ibrahem et al. (2014) solved a scheduling cellular flow shop problem with family sequence-dependent setup time to minimize the total flow time using two meta-heuristic algorithms GA and particle swarm optimization (PSO). Tang et al. (2014) to minimize the total penalty cost of tardiness, solved an integer programming model for the simultaneous problems of CF and scheduling using the Lagrangian relaxation decomposition method. Halat and Bashirzadeh (2015) presented an integer programming model and considered such factors as exceptional elements, intercellular movements, intercellular transportation time, and sequence-dependent family setup times with the objective to minimize the makespan. They proposed a heuristic method based on the GA algorithm to solve the problem in real size. In their research, Rafiei et al. (2016) presented a mixed-integer nonlinear programming model to simultaneously address the problems of CF and job scheduling. To solve their model, they used a novel hybrid GA and SA. Feng et al. (2018) worked out a mixed-integer programming model to address alternative machine allocation, machine sharing, intercellular movement, and flexible routes simultaneously in a DCMS. Their objective is to minimize the maximum completion time and the total workload at the same time. To solve the model, they proposed a three-layer chromosome genetic algorithm. Jawahar and Subhaa (2017) presented a linear and a nonlinear model of designing a CMS with operational and structural decision variables. Furthermore, they developed a GA based on self-regulating adaptive operators to solve the proposed model. They used an adjustable grouping genetic algorithm (AGGA) to solve their model. Ebrahimi et al. (2016) presented a model in which the problems of layout and scheduling are dealt with simultaneously in a CMS. The model includes several features of CMS models, including a due date, material handling time, operation sequence, processing time, unequal-area facilities (with different dimensions), and parts scheduling. They developed a GA to solve the model in large sizes. Alimian et al. (2020) combined CF, GS, production planning, and preventive maintenance by presenting a mathematical model for a DCMS. For the implementation of preventive maintenance operations, the periods are divided into M subperiods. Saddikuti and Pesaru (2019) formulated an NSGA algorithm to minimize flow time, makespan, idle time, and energy consumption in the cellular manufacturing environment. In the scheduling model proposed by Subhaa et al. (2019), the objective is to minimize machine utility costs and intercellular material handling. To reduce the machine utility costs, the completion time is considered as the time of using the machines. They used a hybrid SA and a GA to solve the model in large sizes. Wang et al. (2019b) proposed an integer linear programming mathematical model to simultaneously deal with the problems of CF and scheduling. In this model, multi-skilled workers are assigned to machines, and it is possible to move among the machines. In his study, Zandieh (2019) addressed the problem of scheduling in a VCMS to reduce the weighted sum of the makespan and the total distance traveled by jobs.

Most of the existing studies on scheduling problems in CMSs have been done recently. Moreover, many mathematical models have been introduced for these problems so far. As a part of its objectives, the model presented in this paper, too, solves a scheduling problem in a CMS. It deals with alternative processing routes, connected periods, the possibility of receiving an order at any time and machine relocation time. Furthermore, CF is done at the same time as scheduling. Table 2 compares the articles in the literature with the model presented in this article.

Table 2 Comparison of the model in this study and those reported in the literature

3 Mathematical modeling

This section of the paper provides an analysis of the bi-objective nonlinear integer programming mathematical model by explaining the objective functions and constraints. Then, the model is linearized.

3.1 Model description

The issues of CF, GS, order acceptance, pricing, and delivery time determination are decided on simultaneously in the problem studied in this paper. The problem is concerned with a CMS which involves some cells, machines, and parts. Each part requires several operations, and there are alternative processing routes to perform the operations. The time of the operations on the machines is deterministic. Moreover, each machine has a certain time capacity. The problem is solved periodically as to separate the orders better. The orders that arrive at the factory in a period are classified in the next period after a certain time. The periods are connected, and it is possible to receive the order at any time. Some of the orders are new, and the model must decide whether to accept or reject them based on the capacity and schedule of the existing orders. The delivery time and the price of the existing orders are specified, and those of new orders are determined by the model. Idle machines can be moved during any period, and the time and the cost of relocation are taken into consideration. The proposed nonlinear model has two objectives including profit maximization (considering earliness and tardiness penalty, machine relocation costs, intracellular and intercellular material handling costs, and operating costs) and maximizing the number of orders accepted.

Assumptions:

• Machine processing times are known and deterministic.

• Only one operation of any part can be processed on the machine at a time.

• Each operation of each part is performed only on one machine.

• There is no possibility of interruption in operations.

• Machine breakdowns are not taken into consideration.

• The upper and the lower bounds of the cells are fixed.

• The arrival time of the orders is known.

• Setup time is not taken into consideration.

Sets

$k=\left\{1, 2, \dots , K\right\}$ :

Set of operations

$p = \left\{ {\overbrace {{1,2, \ldots ,P_{{old}} }}^{{Oldparts}},\;\overbrace {{...,P}}^{{Newparts}}} \right\}$ :

Set of parts, including the existing and new parts

$h=\left\{1, 2, \dots , H\right\}$ :

Set of periods

$s=\left\{1, 2, \dots , S\right\}$ :

Set of scenarios for a new part or a new order

$m=\left\{1, 2, \dots , M\right\}$ :

Set of machines

$c=\left\{1, 2, \dots , C\right\}$ :

Set of cells

$j=\left\{1, 2, \dots , J\right\}$ :

Set of time units

Parameters

$LB$ :

Lower cell size limit

$UB$ :

Upper cell size limit

${TM}_{m}$ :

The capacity of machine type m

${\gamma }_{p}$ :

Inter-cell material handling cost for part type p

${\lambda }_{p}$ :

Intra-cell material handling cost for part type p

${\theta }_{m}$ :

Machine relocation cost for machine type m

${\rho }_{m}$ :

The processing cost of machine type m per unit time

${Pr}_{phs}$ :

The selling price of part p of period h under scenario s

${IA}_{p}$ :

Intra-cell material handling time for part type p

${IE}_{p}$ :

Inter-cell material handling time for part type p

${RT}_{m}$ :

Machine relocation time for machine type m

${e}_{kpm}$ :

Processing time of operation k of part p on machine m

${Pw}_{p}$ :

Percentage of the importance of new part p for production

${d}_{ph}$ :

1 if there is a demand for part p in period h. Otherwise, 0

${du}_{phs}$ :

Due date of part p in period h under scenario s

${A}_{ph}$ :

Arrival time of order p

${\alpha }_{ph}$ :

The unitary tardiness penalty of part p in period h

${\beta }_{ph}$ :

The unitary earliness penalty of part p in period h

${q}_{kpm}=\left\{\begin{array}{c}1\\ \\ 0\end{array}\right.$ :

If operation k of part p needs machine type m Otherwise,

MM :

An arbitrary big positive number

Decision variables

${X}_{kphmj}$:

1 if operation k of part p in period h is being processed on machine m, at time j. Otherwise, 0

${Z}_{kphmc}$:

1 if operation k of part p in period h is processed on machine m and in cell c. Otherwise, 0

${W}_{mcj}$:

1 if machine m belongs to cell c at time j. Otherwise, 0

${Ac}_{phs}$:

1 if part p in period h is accepted under scenario s. Otherwise, 0

${ST}_{kphm}$:

The start time of operation k of part type p in period h on machine m.

${CO}_{kphm}$:

Completion time of operation k of part type p in period h on machine m.

${T}_{ph}$:

Tardiness of part p in period h.

${E}_{ph}$:

Earliness of part p in period h.

${C}_{ph}$:

Completion time of part p in period h.

Mathematical model

$$Max\; {Z}_{1}=\sum_{p=1}^{P}\sum_{h=1}^{H}\sum_{s=1}^{S}{Pr}_{phs}{Ac}_{phs}$$

(1.1)

$$-\sum_{p=1}^{P}\sum_{h=1}^{H}\left({\alpha }_{ph}{T}_{ph}+{\beta }_{ph}{E}_{ph}\right)$$

(1.2)

$$-\frac{1}{2}.\sum_{c=1}^{C}\sum_{j=1}^{J-1}\sum_{m=1}^{M}{\theta }_{m}.\left|{W}_{mcj}-{W}_{mc,j+1}\right|$$

(1.3)

$$ -\sum\limits_{{k = 1}}^{K} {\sum\limits_{{p = 1}}^{P} {\sum\limits_{{h = 1}}^{H} {\sum\limits_{{m = 1}}^{M} {\sum\limits_{{m^{{\prime }} = 1}}^{M} {\sum\limits_{{c = 1}}^{C} {\sum\limits_{{c^{{\prime }} \ne c}}^{C} {\gamma _{p} .Z_{{kphmc}} .Z_{{k + 1,\;phm^{{\prime }} c^{{\prime }} }} } } } } } } } $$

(1.4)

$$-\sum_{k=1}^{K}\sum_{p=1}^{P}\sum_{h=1}^{H}\sum_{m=1}^{M}\sum_{{m}^{^{\prime}}\ne m}^{M}\sum_{c=1}^{C}{\lambda }_{p}.{Z}_{kphmc}.{Z}_{k+1,ph{m}^{^{\prime}}c}$$

(1.5)

$$-\sum_{m=1}^{M}\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{P=1}^{P}\sum_{j=1}^{J}{\rho }_{m}.{X}_{kphmj}$$

(1.6)

The first objective function maximizes the profit from production. In component (1.1), the revenue from the sale is calculated, and in the next expressions, the estimated costs are deducted from the revenue. These costs include the following five components:

Equation (1.2) calculates the sum of tardiness and earliness cost for all the parts in all the periods. The tardiness penalty, in addition to the penalties in the contract, includes the cost of losing credibility, and the earliness penalty includes warehousing costs. Equation (1.3) calculates the machine’s relocation cost. Equations (1.4) and (1.5) calculate the intercellular and intracellular material handling costs, respectively. Equation (1.6) calculates the operating cost of all the machines.

$$Max\; {Z}_{2}=\sum_{p=1}^{P}\sum_{h=1}^{H}\sum_{s=1}^{S}{Pw}_{p}{Ac}_{phs}$$

(1.7)

The second objective function is to maximize the number of the new parts produced based on their priority, as shown in Eq. (1.7). This factor includes the importance of the customers that order those parts, the importance of the parts in the growth rate of the factory market share, and other market-based factors. These are dealt with by the marketing department through weighting.

Subject to:

$$ \mathop \sum \limits_{m = 1}^{M} \mathop \sum \limits_{c = 1}^{C} q_{kpm} .Z_{kphmc} = d_{ph} .\mathop \sum \limits_{s = 1}^{S} Ac_{phs} \quad \quad \forall k,p, h; $$

(2)

$$ \mathop \sum \limits_{s = 1}^{S} Ac_{phs} = 1\quad \quad \forall p \in O, h; $$

(3)

$$ X_{kphmj} \le \mathop \sum \limits_{c = 1}^{C} Z_{kphmc} \quad \quad \forall k,p,h, m, j; $$

(4)

$$ Z_{kphmc} \le \mathop \sum \limits_{j = 1}^{J} X_{kphmj} .W_{mcj} \quad \quad \forall k,p,h, m, c; $$

(5)

Equation (2) states that each operation of each part can only be performed on one of the machines capable of performing that operation and in only one of the cells. Of course, if there is a demand for that part. For new parts, the condition of accepting that part under only one of the scenarios is also considered. Equation (3) shows which parts must be produced, and the model will not decide whether to accept or reject them. In this model, some parts of the orders have already been accepted, and the others are the new orders that have to be decided. Constraint (4) states that, if the operation k of part P in period h at time point j is on machine m, it must be located in one of the cells. Constraint (5) states that, if the operation k of part P is performed in period h in cell c on machine m, that machine must also be present in the cell at the time of processing the corresponding operation of that part.

$$ \mathop \sum \limits_{j = 1}^{J} X_{kphmj} = e_{kpm} .d_{ph} .\mathop \sum \limits_{c = 1}^{C} Z_{kphmc} \quad \forall k,p,h, m; $$

(6)

$$ \mathop \sum \limits_{k = 1}^{K} \mathop \sum \limits_{h = 1}^{H} \mathop \sum \limits_{P = 1}^{P} X_{kphmj} \le 1 \quad \forall m,j; $$

(7)

$$ X_{1phmj} = 0 \quad \forall p, h,m, c, j \le A_{ph} ; $$

(8)

$$ \mathop \sum \limits_{k = 1}^{K} \mathop \sum \limits_{h = 1}^{H} \mathop \sum \limits_{P = 1}^{P} \mathop \sum \limits_{j = 1}^{J} X_{kphmj} \le TM_{m} \quad \forall m; $$

(9)

Equation (6) ensures that the sum of the time positions in which the operation k of part p in period h is processed on machine m is equal to the operation time of that part on that machine. Constraint (7) indicates that, on any machine at any time, only one operation of one part can be processed. Constraint (8) holds that the start time of the first operation of each part must be after the arrival of the order at the factory. Constraint (9) ensures that the total production time on a machine is less than the capacity of that machine.

$$ \mathop \sum \limits_{c = 1}^{C} W_{mcj} \le 1\quad \forall m, j; $$

(10)

$$ MM\left( {1 - W_{mcj^{\prime}} } \right) \ge \mathop \sum \limits_{j = j^{\prime}}^{{j^{\prime} + RT_{m} }} W_{mc^{\prime}j} \quad \forall m, c,c^{{\prime }} \ne c, j^{{\prime }} ; $$

(11)

$$ X_{kphmj} \le \mathop \sum \limits_{c = 1}^{C} W_{mcj} \quad \forall k, p,h,m, j; $$

(12)

Constraint (10) states that each machine can belong to only one cell at each point of time. Constraint (11) states that it does not belong to any cell during the time the machine is moving from one cell to another. Constraint (12) states that the operation k of part p in period h can be on machine m at time position j only if machine m is present in one of the cells at that point of time.

$$ \mathop \sum \limits_{m = 1}^{M} W_{mcj} \le UB\quad \forall c, j; $$

(13)

$$ \mathop \sum \limits_{m = 1}^{M} W_{mcj} \ge LB\quad \forall c, j; $$

(14)

Constraints (13) and (14) show the upper and the lower bounds of each cell, respectively.

$$ CO_{kphm} = \mathop {\max }\limits_{j} (X_{kphmj} .j)\quad \forall k, p, h, m; $$

(15)

$$ ST_{kphm} = \mathop {\min }\limits_{j} \left[ {j + MM\left( {1 - X_{kphmj} } \right)} \right]\quad \forall k, p, h, m; $$

(16)

$$ CO_{kphm} - ST_{kphm} = \left( {e_{kpm} - 1} \right).\left( {\mathop \sum \limits_{c = 1}^{C} Z_{kphmc} } \right).d_{ph} \quad \forall k, p, h, m; $$

(17)

$$ CO_{kphm} \le MM. \mathop \sum \limits_{c = 1}^{C} Z_{kphmc} \quad \forall k, p, h, m; $$

(18)

$$ ST_{kphm} \le MM. \mathop \sum \limits_{c = 1}^{C} Z_{kphmc} \quad \forall k, p, h, m; $$

(19)

Equation (15) calculates the completion time of the operation k of part p in period h on machine m. Equation (16) calculates the start time of the operation k of part p in period h on machine m. Equation (17) ensures that one operation remains on a machine from the beginning to the end of the operation. This means that there is no possibility of interruption during an operation. According to constraints (18) and (19), variables ${CO}_{kphm}$ and ${S}_{kphm}$ can take a value greater than zero if the operation k of part P is performed in period h on machine m in one of the cells. Otherwise, their value will be zero.

$$ ST_{kphm} \ge CO_{{k - 1,phm^{\prime}}} + MM.\left[ {\left( {\mathop \sum \limits_{c = 1 \ne c^{\prime}}^{C} Z_{kphmc} } \right) - 1} \right] + IE_{p} .Z_{kphmc} .Z_{{k - 1,phm^{\prime}c^{\prime}}} \quad \forall k, p, h, m,m^{\prime},c, c^{\prime} \ne c; $$

(20)

$$ ST_{kphm} \ge CO_{{k - 1,phm^{\prime}}} + MM.\left[ {\left( {\mathop \sum \limits_{c = 1}^{C} Z_{kphmc} } \right) - 1} \right] + IA_{p} .Z_{kphmc} .Z_{{k + 1,phm^{\prime}c}} \quad \forall k, p, h, m,m^{\prime} \ne m, c; $$

(21)

$$ ST_{kphm} \ge CO_{k - 1,phm} + MM.\left[ {\left( {\mathop \sum \limits_{c = 1}^{C} Z_{kphmc} } \right) - 1} \right] + 1\quad \forall k, p, h, m $$

(22)

According to constraint (20), if a part is moved between two cells, the start time for the operation of that part on a machine in one cell must be greater than the sum of the completion time of the previous operation of that part in another cell and the intercellular movement time. Constraint (21) holds that, if a part is moved within a cell, the start time for the operation of that part on the machine must be greater than the sum of the completion time of the previous operation of that part on another machine and the intracellular movement time. As constraint (22) postulates, if two consecutive operations of a part are performed on one machine, the start time of the next operation must be longer than the completion time of the previous operation of that part.

$$ C_{ph} = \mathop \sum \limits_{m = 1}^{M} CO_{Kphm} \quad \forall p, h; $$

(23)

$$ T_{ph} \ge C_{ph} - \mathop \sum \limits_{s = 1}^{S} Ac_{phs} .du_{phs} \quad \forall p, h; $$

(24)

$$ E_{ph} \ge \mathop \sum \limits_{s = 1}^{S} Ac_{phs} .du_{phs} - C_{ph} \quad \forall p, h; $$

(25)

$$ X_{kphmj} ,W_{mcj} , Z_{kphmc} ,Ac_{phs} \in \left\{ {0,1} \right\}\quad \forall k, p,h,m, c, j, s; $$

(26)

$$ T_{ph} , E_{ph} , C_{ph} , ST_{kphm} ,CO_{kphm} \ge 0\quad \forall k, p, h, m; $$

(27)

Constraint (23) calculates the completion time of part p in period h. Constraints (24) and (25) calculate the tardiness and earliness of each part in each period, respectively, according to the scenario in which the part is accepted. Constraints (26) and (27) indicate the types of decision variables.

3.2 Linearization of the proposed model

The equations which are nonlinear in the proposed model are linearized. To linearize Eq. (1.4), the absolute term $\left|{W}_{mcj}-{W}_{mc,j+1}\right|$ is substituted with the sum of the auxiliary variables ${WP}_{mcj}+{WM}_{mcj}$, and the following constraint is added to the constraint set:

$$ W_{mcj} - W_{mc,j + 1} = WP_{mcj} - WM_{mcj} \quad \forall m, c, j; $$

(28)

To linearize Eq. (1.5) and constraint (20), the transformation $Z_{{kphmc}} .Z_{{k + 1,\;phm^{{\prime }} c^{{\prime }} }} {\text{ = Y}}_{{{\text{kphmm}}^{{\prime }} cc^{{\prime }} }}$ is done, and the following constraint is added to the main model:

$$ Y_{kphmm^{\prime}cc^{\prime}} \ge Z_{kphmc} + Z_{k + 1,phm^{\prime}c^{\prime}} - 1.5\quad \forall k,p,h,m,m^{{\prime }} , c \ne c^{{\prime }} ; $$

(29)

To linearize Eq. (1.6) and constraint (21), the transformation $Z_{{kphmc}} .Z_{{k + 1,\;phm^{{\prime }} c^{{\prime }} }} {\text{ = Y}}_{{{\text{kphmm}}^{{\prime }} c^{{\prime }} }}$ is done, and the following constraint is added to the main model:

$$ Y1_{kphmm^{\prime}c} \ge Z_{kphmc} + Z_{k + 1,phm^{\prime}c} - 1.5\quad \forall k,p,h,m \ne m^{{\prime }} , c; $$

(30)

Nonlinear constraint (5) can be linearized by the transformation ${X}_{kphmj}.{W}_{mcj}={X1}_{kphmcj}$, and the following sets of constraints must be added to the main model:

$$ X1_{kphmcj} \le X_{kphmj} \quad \forall k, p, h, m,c, j; $$

(5.1)

$$ X1_{kphmcj} \le W_{mcj} \quad \forall k, p, h, m,c, j; $$

(5.2)

$$ X1_{kphmcj} \ge X_{kphmj} + W_{mcj} - 1.5\quad \forall k, p, h, m,c, j; $$

(5.3)

The auxiliary variable ${F}_{kphmj}$ is used to linearize constraint (15), and the following set of constraints is added to the model:

$$ F_{kphmj} \le j + MM\left( {1 - X_{kphmj} } \right)\quad \forall k, p, h, m, j; $$

(15.1)

$$ F_{kphmj} \ge j - MM\left( {1 - X_{kphmj} } \right)\quad \forall k, p, h, m, j; $$

(15.2)

$$ F_{kphmj} \le MM.X_{kphmj} \quad \forall k, p, h, m, j; $$

(15.3)

$$ Co_{kphm} \ge F_{kphmj} \quad \forall k, p, h, m, j; $$

(15.4)

The auxiliary variables ${U}_{kphmj}$ and ${B}_{kphmj}$ are used to linearize constraint (16), and the following set of constraints is added to the model:

$$ ST_{kphm} = J - \mathop \sum \limits_{j}^{J} B_{kphmj} + 1 - \left( {J + 1} \right).\left( {1 - Z_{kphm} } \right)\quad \forall k, p, h, m; $$

(16.1)

$$ B_{kphm1} = X_{kphm1} \quad \forall k, p, h, m; $$

(16.2)

$$ B_{kphmj} = B_{kphm,j - 1} + \left( {1 - B_{kphm,j - 1} } \right).X_{kphmj} \quad \forall k, p, h, m, j; $$

(16.3)

Equation (16.3) is linearized with the substitution of ${B}_{kphm,j-1}.{X}_{kphmj}={U}_{kphmj}$, and the following set of constraints is added to the model:

$$ U_{kphmj} \le B_{kphm,j - 1} + MM\left( {1 - X_{kphmj} } \right)\quad \forall k,{ }p,{ }h,{ }m,{ }j; $$

(16.4)

$$ U_{kphmj} \ge B_{kphm,j - 1} - MM\left( {1 - X_{kphmj} } \right)\quad \forall k,{ }p,{ }h,{ }m,{ }j; $$

(16.5)

$$ U_{kphmj} \le MM.X_{kphmj} \quad \forall k,{ }p,{ }h,{ }m,{ }j; $$

(16.6)

4 NSGA-II algorithm

Since the problems of scheduling and DCMS fall in the category of NP-hard problems, it is necessary to use meta-heuristic methods (Solimanpur and Elmi 2013; Dehnavi-Arani et al. 2020; Shafiee-Gol et al. 2021).There are two categories of methods for solving multi-objective problems. By the first, an integrated objective function is created from the weighted sum of the objective functions, and only one optimal solution is obtained for the problem. In the second category, a set of solutions called Pareto solutions is obtained. All the studied multi-objective models dealing with the problem of scheduling in cellular production systems have been solved with GA family. Therefore, in this paper, an NSGA-II is designed to solve the problem and find Pareto solutions. To evaluate the efficiency and accuracy of the designed algorithm, its solutions are compared with those obtained from the augmented epsilon constraint method, in which the GAMS software is used for problem solving.

4.1 Chromosome structure and initial population

Designing a suitable structure for the initial population is one of the most critical tasks when using meta-heuristic algorithms. In this study, a non-repetitive random structure is used to generate the initial population. Since it is hard to guarantee the validity of the answers using random numbers without making corrections, a correction model is used based on the constraints of the mathematical model. In general, the structure to display answers is in the form of the matrix $\left(M\times J\right)$, in which each cell is assigned an integer number in the range $\left[0,\left|P\times K\times H\times C\times S\right|\right]$. In this matrix, the numbers in each column must be non-repetitive and subject to permutation. The structure of this answer is given in Figs. 1, 2.

Fig. 1

Features of the proposed model

Fig. 2

Structure of the answer

It should be noted that $\left|P\times K\times H\times C\times S\right|$ means all the possible states are based on complete counting which occurs in a preprocessing procedure. In this procedure, of course, machines that are not capable of performing an operation will be removed from the set. In fact, at this stage of preprocessing, constraint (2) is guaranteed. It is also important to note that there can only be one scenario in each response matrix, for each constant $P$ and different $K$. To guarantee this condition, in the preprocessing section, all the members with the same $P$ and a different $S$ are placed in one set. It is clear that only one member of each set in each matrix can be located in the matrix cells. In other words, the members of any set with a constant $P$ and a different $S$ are equivalent, and the first member of that set can be placed in the response matrix. Since J indicates the processing time, the first column of the response matrix is considered as a criterion for performing calculations related to the response correction section. For this purpose, according to the time required to perform the operation in each part, the number in each matrix cell is repeated in the subsequent cells. For example, if the processing time of the first operation in the first part on the first machine is 3, the matrix is modified as in Fig. 3.

Fig. 3

Structure of the answer after modification

Therefore, the calculations are continued starting from cell number 4. During this process, the operations for each part must be correctly sequenced. For this purpose, in each response matrix cell, it is checked whether or not the constraint is met. If it is not met, a number larger than that in the last cell will be replaced, provided it is non-repetitive in the corresponding column. If the existing answer is still infeasible, zero is placed in that cell, and the number in the next cell is checked. Considering the ascending order of the members in the collection $\left|P\times K\times H\times C\times S\right|$, the response with a larger number guarantees the next operation of a part. Another constraint that needs to be considered is the movement of parts and machines. For this purpose, the largest value between the movement time of the machine and the part is taken as the start time of the next operation in the response matrix. The completion time of an operation on a machine maybe 10, but the start time of the next operation is 14. This number results from calculations to determine the largest value between the movement time of the machine and the part. Thus, at the interval of 10 to 14, a value of zero can be assigned to the cells, indicating that the machine is idle. Using this procedure, it can be ensured that the generated responses are justified, and thus, the steps to improve the responses are possible.

4.2 Crossover structure

In this study, a two-point crossover operator is used in which two different responses are selected as parents and then cut from two random points in the columns of the matrix. The cut sections of the matrix are joined together to produce two new offspring instances. Figure 4 shows this structure.

Fig. 4

Crossover operator

The offspring instances produced by the crossover operator must be re-examined and corrected. If they are feasible and have high fitness, they can be used in the next generation.

4.3 Mutation structure

The application of the mutation operator is based on a displacement structure with two columns of the response matrix selected and moved together. Figure 5 shows this structure.

Fig. 5

Mutation operator

4.4 Parameter setting of the proposed algorithm

The NSGA-II algorithm has four key parameters including the size of population, the number of iterations, mutation rate and crossover rate. To improve the performance of algorithms in solving different numerical examples, it is necessary to determine the optimal levels of these parameters. This research makes use of the experimental design method based on the response surface method (RSM). Since the research problem has two objective functions, a single answer cannot directly quantify the response variable. Therefore, the response variable (R_i as in Eq. 30) is a combination of five criteria to compare multi-objective algorithms. The criteria include the number of Pareto solutions (NPSs), medium ideal distance (MID), spacing, diversity and CPU time. However, these criteria are not equally important to the decision-maker. Table 3 shows the weight of each criterion.

Table 3 Weight of each criterion

$${R}_{i}=\frac{{w}_{1}\overline{{RPD }_{1}}+{w}_{2}\overline{{RPD }_{2}}+ \cdots + {w}_{n}\overline{{RPD }_{n}}}{{w}_{1}+{w}_{2}+\cdots +{w}_{n}}$$

(31)

As Eq. (31) suggests, to calculate the response variable ${R}_{i}$, the relative percentage deviation (RPD) is used for each problem.

$$RPD=\frac{{Alg}_{sol}-{Min}_{sol}}{{Min}_{sol}}\times 100$$

(32)

The range of each parameter in the proposed algorithm is presented in Table 4.

Table 4 Low, medium, and high levels of the proposed algorithm parameters

The experiments are performed by the RSM method using the Design Expert 12 software. The optimal levels of the parameters in the proposed algorithm are presented in Table 5.

Table 5 Optimal levels of the parameters

5 Computational results

In this section, firstly the validity of the model is examined by solving a numerical example in small dimension. In the following, through the analysis of the model sensitivity, the effects of key parameters on the problem, and some important features of the model are addressed. At the end of each part of the sensitivity analysis, insights are provided for managers to use in practical decisions. Finally, the performance of the proposed algorithm is examined by solving different numerical examples. It is noteworthy that the examples provided using CPLEX solver of GAMS software have been solved with an exact method and NSGA-II algorithm is implemented in MATLAB software environment. The examples have been solved on a personal computer with Intel® Core ™ i7-4850HQ 2.30 GHz CPU and 16.0 GB RAM.

5.1 Illustrative numerical example

To validate the model, a numerical example with a set of random-generated data is solved using the GAMS software in 761 s. The proposed model has two objectives, but only the first objective, which is more important, is taken into account to explore the features of the model and perform the sensitivity analysis. The number of the variables and the constraints of this problem is 49123 and 118,323, respectively. This example makes use of 11 parts (including six new parts and five existing parts), two operations, six machines, two cells, two periods, and 28 time positions. For some new orders, three scenarios are also used. The cost and the time of handling the intracellular and intercellular materials are given in Table 6, and Table 7 presents the data about the machines.

Table 6 Data on the relocation times and costs of the parts

Table 7 Machine data

Table 8 shows the processing time data. The second operation of part 5 can be performed on machines 4 and 5 with times 7 and 4, respectively. Table 9 provides the data on the orders. The results are presented in Table 10 and Fig. 6.

Table 8 Processing time data

Table 9 Data of the orders

Table 10 Cost components and the optimal solution for example 1

Fig. 6

Scheduling of the parts for example 1

The new orders that have been accepted and their accepted scenario are shown in Tables 11, 12. For example, in period one, the decision is made to produce part 6, and this part is accepted for production under the second scenario out of three available ones. During this period, part 10 is not produced. In the case of part 8, it is assumed that there is no possibility of negotiation for the price and delivery time. So, there is no scenario for the production of this part. Figure 6 shows which cell each machine belongs to at any point in time. It also shows the scheduling of the parts on the machines. In this example, an intercellular shift occurs for part 2 in period 2 from cell 1 to cell 2. Also, machine 5 is used in cell 2 until time 6, and then, it is used by spending two units of time in time 9 in cell 1. The tardiness and earliness times of each part can also be seen in the figure. For example, part 9 in period 1 has one unit of tardiness time, and part 4 in period 2 has two units of earliness time (Tables 13, 14, 15, 16, 17, 18, 19).

Table 11 Accepted scenario for the new orders in example 1

Table 12 Cost components and the optimal solution for example 2

Table 13 Accepted scenario for the new orders in example 2

Table 14 Cost components and the optimal solution for example 3

Table 15 Accepted scenario for the new orders in example 3

Table 16 Cost components and the optimal solutions for examples 4.1, 4.2 and 4.3

Table 17 Accepted new orders in examples 4.1, 4.2 and 4.3

Table 18 Cost components and the optimal solutions for examples 5.1 and 5.2

Table 19 Accepted scenario for the new orders in examples 5.1 and 5.2

5.2 Sensitivity analysis and managerial insights

5.2.1 Scheduling new orders assuming that the existing schedule is fixed

Example 2

Assume that, like most order acceptance structures mentioned in the literature, new order scheduling must be performed without changing the existing order schedule. To do this, the problem must first be scheduled without the new orders considered. Then, the values obtained are considered constant, and the problem of scheduling and accepting the new orders is solved. In this case, the values of the objective function will be as follows:

The results suggest the following point:

• In this case, not only the factory's profit but also the number of the accepted new orders is decreased. Therefore, the integrated scheduling of the existing parts with the new orders increases the factory's profit.

5.2.2 Accepting all the orders

Example 3

The problem is examined in case the factory has to accept all the new orders.

The results suggest the following points:

• There is enough capacity to produce all the parts, but the model does not consider it economical to produce some.

• In most articles on order acceptance in the MTO environment, if a part is valuable in terms of the marketing and the factory capacity is sufficient, it is scheduled in the factory. Therefore, it seems that the integration of these decisions can be beneficial for the factory.

• An order may have a reasonable price and there may be sufficient capacity to produce it, but scheduling it with other orders increases production costs and delivery time.

5.2.3 Impossibility of negotiating

When a new order is offered to the company's marketing department, it may be negotiable or non-negotiable. Non-negotiable orders have a fixed price and delivery time. However, for negotiable orders, there is a possibility of bargaining and offering lower prices. It may also be possible to get more time from the customer for delivery, thus allowing more orders to be accepted. In this model, negotiation for the price and delivery time of the order is possible by defining different scenarios.

This section of the study examines the model without the possibility of negotiating to show the effect of this feature better. For this purpose, the problem is solved in three different cases, assuming that one of the scenarios is fixed for all the negotiable orders. The first case is a higher price and earlier delivery time, the third case is later delivery time and a lower price, and the second case is the average of the other two.

Example 4.1

Considering the higher price and earlier delivery time for all the new orders (first case).

Example 4.2

Considering the average price and delivery time for all the new orders (second case).

Example 4.3

Considering the lower price and later delivery time for all the new orders (third case).

The results suggest the following points:

• A comparison of the above three cases shows that, if managers can increase the delivery time when negotiating with customers, they can produce more products. In other words, they can increase their market share.

• A comparison of the above three cases with the original example shows that negotiation can be effective in increasing the profit and market share.

5.2.4 Offering new orders during production and not at the beginning

One of the special features of this model is the ability to check the rejection or acceptance of a new order at any point of time, which is shown in the following examples.

Example 5.1

Parts 2 and 7 of the second period are offered to the production department at the time t = 7.

It is assumed that the new schedule can be applied from the time t = 8. So, the model is first solved by the assumption that there are no new orders 2 and 7. Assuming the absence of orders 2 and 7, it may be decided to produce some new orders. In this case, considering that an agreement has been reached with the customer, at the time of reviewing orders 2 and 7, these orders must be produced. Moreover, as assumed, it is only possible to change the scenario for them. For example, in the original problem where the acceptance or rejection of the new orders is decided at the beginning of planning, part 8 is not accepted in the second period, but here it is accepted and must be produced.

Example 5.2

Parts 8 and 9 of the second period are offered to the production department at the time t = 10.

It is assumed that the new schedule can be applied from the time t = 11. So, the model is first solved by the assumption that there are no new orders 8 and 9. Assuming the absence of orders 8 and 9, it may be decided to produce some new orders. In this case, considering that an agreement has been reached with the customer, at the time of reviewing orders 8 and 9, these orders must be produced. Furthermore, as assumed, it is not possible to change the scenario for them. In this example, despite the fact that the accepted orders and the accepted scenarios are the same as in example 1, the profit has decreased. This is because, in example 1, all the orders are scheduled together, while the scheduling has been done here since t = 11.

The results suggest the following points:

• The feature mentioned in this section helps decision makers to decide whether to reject or accept an order at any time but not necessarily at the beginning of the planning horizon. They can also optimize the machine layout, scheduling and sequencing if a new order is accepted.

• The shorter the time interval between the start of the production program and the arrival time of the new order, the more chances decision makers will have to accept the order.

5.3 Evaluation of the proposed NSGA-II algorithm efficiency

In this section, two different types of analysis are performed in order to evaluate the efficiency of the algorithm. First, the example presented in Sect. 5.1 (E4) is solved with the proposed algorithm, and the results are compared with those obtained from the augmented epsilon constraint method. Second, a number of numerical examples are generated with random input data, and the results of the algorithm and the mathematical model are compared using mean ideal distance (MID) provided by Karimi et al. (2010).

According to the results presented in Table 20, the Pareto frontiers obtained from the proposed algorithm largely correspond to those obtained from the augmented epsilon constraint method, while requiring much less CPU time.

Table 20 Pareto solution for example E4

Moreover, as shown in Fig. 7, the Pareto members obtained by CPLEX and NSGA-II are significantly close to each other. In fact, NSGA-II can achieve reliable near-optimal solutions.

Fig. 7

Comparison of CPLEX and NSGA-II Pareto front

To compare the proposed algorithm and the epsilon constraint method in terms of the CPU time, ten other examples (E1–E10) are solved, and the results are presented in Table 21. It is obvious that NSGA-II can provide appropriate solutions in an acceptable time.

Table 21 Comparison of the NSGA-II and epsilon constraint solutions

According to Fig. 8, the CPU time of CPLEX is increased exponentially compared to that of NSGA-II with a linear trend when the dimension of the instances increases. Moreover, CPLEX can only solve instances E1 to E5, while NSGA-II is able to solve all the instances within an acceptable time.

Fig. 8

Comparison of CPLEX and NSGA-II in terms of the CPU time

As mentioned before, the performance of heuristic/meta-heuristic algorithms should be examined from different perspectives such as the distance from the ideal optimal solution (Datta and Figueira 2012). This distance is one of the most important criteria widely used to measure the performance of algorithms. So far, various criteria have been presented to measure the distance of the Pareto front produced by the algorithm with the global optimal front. Among them, the Euclidean distance between the Pareto front members from an ideal point is the mostly used one (Li and Yao 2019). In this research, a mathematical structure is used to calculate this distance called ‘the MID criterion.’ It is to be noted that the other criteria presented in the literature serve to calculate the distance between the front of an algorithm and a global optimal front based on this criterion. The Euclidean distance between the final non-dominated solutions generated by the algorithm and the optimal set of solutions generated by CPLEX is calculated according to the following equation:

$$MID=\frac{\sum_{i=1}^{\left|Q\right|}\left(\sqrt{\sum_{j=1}^{{n}_{obj}}{\left(\frac{{f}_{i}^{j}-{f}_{best}^{j}}{{f}_{max}^{j}-{f}_{min}^{j}}\right)}^{2}}\right)}{\left|Q\right|}$$

(32)

where ${f}_{i}^{j}$ represents the ith solution and the jth objective function, ${f}_{best}^{j}$ is the ideal point of the jth objective function, and ${f}_{max}^{j}$ and ${f}_{min}^{j}$ are the maximum and the minimum values of all the Pareto solutions for the jth objective function, respectively. The number of points in the optimal Pareto front is $\left|Q\right|$, and ${n}_{obj}$ is the number of the objective functions. The figure below shows the conceptual view of this index.

Table 22 presents the numerical results. To deepen the analysis of the results, the probability of accepting a solution in the next generation (bal) at the values of 0.2, 0.3 and 0.35% is taken into consideration. The sensitivity of the algorithm to superior solutions in the next generation can be thus examined. This criterion directly affects the ability of the algorithm to pass from the exploration phase to the exploitation phase.

Table 22 Comparison of the results of solving the proposed mathematical model and the algorithm

As it can be seen in the table, for the calculated MID values in small-sized instances, the Pareto front of the algorithm and the optimal front are almost identical. However, the distance increases as the scale becomes larger. Figures 9, 10 show the trend of the MID changes for the bal values.

Fig. 9

Conceptual structure of MID

Fig. 10

MID changes in different values of bal

As shown in Fig. 10, with an increase in the dimensions of the representations, the MID increases at all the bal values. The important point is that, in the largest representation, the MID value is almost equal for all the bal values. This is because the generated solutions do not have significant differences at different bal values. In other words, due to the high size of the numerical instances, the change from exploration phase to exploitation phase in the algorithm cannot significantly change the quality of the final solutions.

In order to more deeply study the behavior of the algorithm and the accuracy of its performance in solving numerical instances, the CPLEX optimization gap is set to 10% and 15% and the results of solving the model with CPLEX and the algorithm are compared. This analysis shows that the proposed algorithm can overcome suboptimal solutions and is able to detect solutions closer to the global optimal. Thus, the small-sized instances presented in Table 23 are performed again considering the 10% and 15% optimization gaps, and the gaps obtained from the MID algorithm and CPLEX are compared.

Table 23 Comparison of numerical results for 10% and 15% optimization gaps

As it can be seen, when the optimization gap increases, the computational gap between the MIDs of CPLEX and the algorithm decreases and, in some cases, becomes negative. A negative value suggests that the front of the algorithm is able to overcome CPLEX solutions and get closer to the ideal point. This indicates the proper performance of the algorithm in finding a near-optimal Pareto front.

6 Conclusion

Designing an agile production system in today's competitive market is very important. A production system must be able to quickly adapt to changes in demand. When orders change, increasing the speed of adaptation of the system can help to increase the speed of production and customer satisfaction. One of the production systems designed for this purpose is the dynamic cellular manufacturing system that is ready to face periodic changes in demand. Considerable research has been done on dynamic cellular manufacturing systems and many practical features have been put forth, but little effort has been taken to speed up adaptation and readiness for new orders.

In this study, a bi-objective schedule is introduced for an OCMS in an MTO environment. The model proposed for this purpose is a mathematical one which integrates CF, GS, order acceptance, pricing, and delivery time. The proposed model includes features such as machine relocation during a period considering the time and cost of movement, sequence of operations, intercellular movement, limitation of cell size, machine capacity, and alternative processing routes. This extended model is able to make optimal decisions on accepting or rejecting a new order, determining the price and delivery time of new orders, scheduling and sequencing the parts on machines, and reconfiguring the cells at any time. The proposed nonlinear model has two objectives including maximizing profits (considering tardiness and earliness penalty, machine relocation costs, intercellular and intracellular material handling costs, and operating costs) and maximizing the number of parts accepted based on their priority. After linearization, the model is solved using the GAMS software and the augmented epsilon constraint method. There are also sensitivity analyses conducted on some features of the model such as the ability to check the rejection or acceptance of new orders at any time and not necessarily at the beginning. With this model, a dynamic online cellular manufacturing system is, thus, developed from a periodic one. The results show that the features of the model can be used to increase productivity, reduce manufacturing costs, and increase customer satisfaction. An NSGA-II algorithm is then designed to solve the model in larger sizes. A comparison of the results obtained from NSGA-II with those of the augmented epsilon constraint method shows the efficiency of the proposed algorithm. For the extension of the current research, the impacts of other issues such as worker assignment, lot splitting, environmental factors, and outsourcing can be examined. In addition, some parameters such as processing time, demands for parts, and machine capacity can be considered uncertain. It is also recommended to use other meta-heuristic methods.