Sage Journals: Discover world-class research

Abstract

This study addresses a part selection problem for flexible manufacturing systems in which part processing times are controllable to optimize the total cost associated with energy consumption, operational performance, and so on. The problem is to determine the set of parts to be produced, part processing times and the number of tools for each tool type in each period of a planning horizon while satisfying processing time capacity, tool magazine capacity and tool life restrictions. The objective is to minimize the sum of part processing, earliness/tardiness, tool and subcontracting costs. Tool sharing among part types is also considered. After an integer programming model is developed, two types of solution algorithms are proposed, that is, fast heuristics useful when decision time is critical and variable neighborhood search algorithms when solution quality is important. Computational experiments were conducted on a number of test instances and the best fast heuristics are specified, together with reporting how much the variable neighborhood search algorithms improve the fast heuristics.

Keywords

Flexible manufacturing systems part selection controllable processing times heuristics

Introduction

The strategic concept of flexible manufacturing emerged to achieve the two conflicting goals of the manufacturing industry, that is, maximizing productivity and flexibility at the same time. In order to realize the concept, various flexible manufacturing systems (FMSs) were implemented during the last several decades and significant amounts of improvement in the aspects of cost, quality, delivery, and flexibility are reported over the world. Now, the flexible manufacturing concept are being evolved into more advanced ones such as reconfigurable manufacturing, smart manufacturing, and so on.^1–6

An FMS can be generally defined as an automated manufacturing system with computer numerical control (CNC) machines, a material handling/storage system and auxiliary facilities, all of which are automatically controlled using a distributed computer control system. Each CNC machine is equipped with an automatic tool changer (ATC) that can automatically interchange cutting tools, which makes an FMS process different part types with high system utilization. However, the capability can be enhanced further when various operational decisions such as planning, scheduling and control are made more efficiently and effectively.

Among various operational problems in FMSs, this study focuses on the part selection problem that determines a set of parts to be produced during an upcoming planning horizon to optimize a certain objective. The problem, alternatively called the batching problem in the literature, is one of pre-release planning that setups parts and tools before an FMS begins to operate. See Stecke,⁷ Kouvelis⁸ and Tempelmeier and Kuhn⁹ for more details on the FMS pre-release planning decisions. Among them, part selection is one of the important ones because the resulting machine loading, resource allocation and scheduling decisions can be made for a given set of parts to be produced.

This study addresses a part selection problem for FMSs in which part processing times are not fixed, but decision variables, called controllable processing times in the literature. Unlike conventional fixed ones, controllable processing times are a practical consideration because there are many situations that job compression is possible while entailing an extra cost, but it is beneficial only if the extra cost is compensated by the gains from earlier job completion.¹⁰ Note that controllable processing times are meaningful in the FMS case when optimizing energy consumption, part precision levels, operational performance, and so on. For example, energy consumption can be optimized by determining appropriate processing times because it is mainly affected by cutting conditions such as cutting depth, feed rate, and cutting speed.^11–14 For a given set of parts to be produced during an upcoming planning horizon, the problem is to determine the set of parts to be produced, together with their processing times, and the number of tools required for each tool type in each period of the planning horizon. The objective is to minimize the sum of part processing, earliness/tardiness, tool and subcontracting costs, where part processing costs depend on processing times under different cutting conditions and the other costs are associated with operational performance. As a practical consideration, tool sharing among different part types is also considered.

The part selection problem considered in this study was motivated from a research project that develops an operating system of an FMS with a state-of-the art numerical control machine that can process high strength parts in high precision levels, called the jig center. From the project, we observed that the precision level and operational performance depend highly on the cutting speed, that is, the precision level increases, but the operational performance decreases as the cutting speed decreases. In addition, tooling requirements such as available tool copies, tool lives and tool sharing must be considered for the part selection module to be applicable to the FMS.

An integer programming model is developed to describe the problem mathematically. After the NP-hardness of the problem is proved, two types of solution algorithms are proposed, that is, fast heuristics and variable neighborhood search algorithms. The fast heuristics obtain an initial solution by a greedy algorithm under given initial part processing times and then improve it by simple local search algorithms with processing time adjustment methods, and variable neighborhood search algorithms improve the fast heuristics by escaping from local optimums. Note that the fast heuristics are useful when decision time is critical while variable neighborhood search algorithms are useful when solution quality is important. In fact, this paper is an improved version of Zeid et al.¹⁵ by explaining the fast heuristics more clearly and proposing additional meta-heuristics to obtain better solutions. To test the performance of the algorithms, computational experiments were conducted on a number of test instances and the test results are reported, that is, performance of the fast heuristics and the amounts of improvement obtained by the variable neighborhood search algorithms.

Literature review

This section reviews the research articles on FMS part selection or batching problems after they are classified into single-period and multi-period approaches. The differences from the previous studies are also explained.

Most previous studies consider single-period problems that determine a set of parts to be produced during an upcoming period. Note that the single-period approach must solve a new problem for the next period after the parts selected in the current period are completed. As an earlier study, Hwang¹⁶ suggests a mathematical programming model for the problem that maximizes the number of products to be produced. Due to its impracticality, Hwan and Shogan¹⁷ extend the earlier model by including part importance and machine capacities. Srivastava and Chen¹⁸ propose tabu search heuristics for the capacitated problem that maximizes the weighted number of products, which is extended by Srivastava and Chen¹⁹ that propose a simulated annealing algorithm for the problem with pallet and fixture limitations. Also, Kim and Yano²⁰ propose a due-date based approach in which that parts are selected using part release priorities determined by approximated schedule information, and Denizel and Sayin²¹ consider the problem for the bi-criterion objective of maximizing the number of parts to be produced and minimizing the total tardiness. See Chen et al.²² and Tabucanon et al.²³ for other single-period models. Besides theses, many articles consider single-period part selection together with machine loading that allocates operations and tools to machines.^24–31

To obtain better solutions over a planning horizon with separated periods, the single-period models are extended to multi-period ones that select the parts to be produced in each period of the planning horizon. As an earlier study, Stecke and Toczylowski³² propose a due-date based model that maximizes the total profit. Also, Lee and Kim³³ consider the problem for the objective of minimizing the sum of earliness, tardiness and subcontracting costs and propose Lagrangean heuristics and later, Zeid et al.¹⁵ extend the earlier problem by considering controllable processing times and propose simple heuristics. As in the single-period case, some articles propose integrated approaches for multi-period part selection and machine loading.^34–39 In particular, Shin et al.³⁹ propose a priority rule based solution approach for multi-period part selection and scheduling in a single-machine FMS with controllable processing times.

As explained earlier, this study improves Zeid et al.¹⁵ by proposing meta-heuristics to obtain better quality solutions. Also, this study is different from Shin et al.³⁹ in that a more concrete part selection problem with controllable processing times is considered for multi-machine FMSs with tool life constraints and tool sharing. Note that the tooling considerations must be incorporated into the problem to obtain practically feasible solutions that can be applied to on-the-spot FMS operations.

Problem description

The FMS considered in this study consists of multiple identical computer numerical control machines, each of which is equipped with a tool magazine of a limited tool slot capacity. See Figure 1 for an FMS with three machines.

Figure 1.

System configuration: an FMS with three machines.

One or more tool types are required to complete a part and a tool type may be used for several part types, called tool sharing. Also, each tool of multiple copies with a limited life is installed on the tool magazines, and each machine, if tooled differently in the tool magazine, can process different part types with negligible setup times. Note that part processing times are discretely controllable, that is, part can be processed according to discretely different processing times with different processing costs, because numerical control machines usually have a finite set of discrete cutting speed modes. It is assumed that part processing times and costs are inverse proportion to each other and given in advance.

For a given set of parts to be produced over an upcoming planning horizon, the problem has three decisions: parts to be produced in each period of the planning horizon; part processing times; and the number of tool copies required for each tool type. Due to system capacities, parts may be subcontracted when not selected within the planning horizon. As the second decision, the processing time of each part is determined by selecting one of the discretely available processing times. Figure 2 shows the part selection and processing time determination decisions. In addition, the number of tool copies for each tool type can be used to estimate the tool requirement for an upcoming planning horizon.

Figure 2.

Multi-period part selection and processing time decisions.

The problem has three types of constraints: processing time capacity; tool magazine capacity; and tool life. First, the processing time capacity implies that the total processing time of the parts selected in a period must not be greater than the aggregated one in that period, that is, period length × number of machines × utilization factor. Next, the tool magazine capacity implies that the total number of tool slots required for the parts to be produced in a period must not be greater than the aggregated one, that is, sum of individual tool magazine capacities. Finally, the tool life constraint implies that the total processing time of the selected parts that require a tool type must not be greater than the total life of the tool type, that is, tool life × number of tool copies.

The objective is to minimize the sum of part processing, earliness/tardiness, tool and subcontracting costs. The processing cost of each part, which may vary for different available processing times, implies the cost to process the part. The earliness cost occurs when a part is processed before its due-date, for example, inventory holding cost, while the tardiness cost occurs if processed after its due-date. It is assumed that the due-date of each part is specified by a period in the planning horizon, that is, the part is due at the end of the period. For example, suppose that the due-date of a part is period 4 in a 10-period problem. Then, an earliness cost occurs if the part is assigned to period 3, while a tardiness cost occurs if the part is assigned to period 5. Also, the tool cost implies the total cost of the tools required to process the selected parts, which is directly proportional to the number of required tools. Finally, the subcontracting cost occurs when parts are not selected within the planning horizon. To maximize the system utilization up to its processing time capacity, it is assumed that the subcontracting cost of a part is always greater than the maximum earliness/tardiness cost of the part.

The problem can be formulated as an integer programming model. Before presenting the model, the notations are summarized below.

Indices

$i$ parts, $i = 1, 2, \dots I$

$j$ available part processing times, $j = 1, 2 \dots, J_{i}$

$t$ tool types, $t = 1, 2 \dots, T$

$h$ periods, $h = 1, 2 \dots, H$

Parameters

$p_{i}^{j}$ $j$ th available processing time of part $i$ , $p_{i}^{1} \leq p_{i}^{2} \leq \dots \leq p_{i}^{J_{i}}$

$d_{i}$ due-date of part $i$

$α_{i}^{j}$ processing cost of part $i$ under $j$ th available processing time, $α_{i}^{1} \geq α_{i}^{2} \geq \dots \geq α_{i}^{J_{i}}$

$β_{ih}$ earliness or tardiness cost of part $i$ incurred when it is assigned to period $h$ , formally,

β_{i h} = {\begin{matrix} ϵ_{i} & \cdot & (d_{i} - h), i f h \leq d_{i} \\ τ_{i} & \cdot & (h - d_{i}), o t h e r w i s e, \end{matrix}

where $ϵ_{i}$ and $τ_{i}$ are per-period early and tardy cost of part $i$ , respectively

$γ_{i}$ subcontracting cost of part $i$

$θ_{t}$ unit cost of tool type $t$

$f_{t}$ number of available copies of tool type $t$

$l_{t}$ life of tool type $t$

$s_{t}$ number of slots required by tool type $t$

$Φ_{t}$ set of parts that require tool type $t$

$Q_{h}$ aggregated processing time capacity in period $h$

$M_{h}$ aggregated tool magazine capacity in period $h$

Decision variables

$x_{ih}^{j}$ = 1 if part $i$ is selected in period $h$ with $j$ th available processing time, and 0 otherwise

$y_{th}$ . number of copies for tool type $t$ used in period $h$

Now, the integer programming model is given below. Note that the following model is an extended one of Lee and Kim³³ by additionally representing controllable processing times and additional tooling considerations.

\begin{matrix} [P] Minimize \sum_{i = 1}^{I} \sum_{j = 1}^{J_{i}} \sum_{h = 1}^{H} (α_{i}^{j} . x_{ih}^{j}) \\ + \sum_{i = 1}^{I} \sum_{j = 1}^{J_{i}} \sum_{h = 1}^{H} (β_{ih} . x_{ih}^{j}) \\ + \sum_{t = 1}^{T} \sum_{h = 1}^{H} (θ_{t} \cdot y_{th}) + \sum_{i = 1}^{I} \\ {γ_{i} . (1 - \sum_{j = 1}^{J_{i}} \sum_{h = 1}^{H} x_{ih}^{j})} \end{matrix}

subject to

\sum_{j = 1}^{J_{i}} \sum_{h = 1}^{H} x_{i h}^{j} \leq 1 for all i = 1, 2, \dots I

(1)

\sum_{i = 1}^{I} \sum_{j = 1}^{J_{i}} p_{i}^{j} . x_{i h}^{j} \leq Q_{h} for all h = 1, 2, \dots H

(2)

\sum_{t = 1}^{T} s_{t} \cdot y_{t h} \leq M_{h} for all h = 1, 2, \dots H

(3)

\sum_{h = 1}^{H} y_{t h} \leq f_{t} for all t = 1, 2, \dots T

(4)

\begin{matrix} \sum_{i \in Φ_{t}} \sum_{j = 1}^{J_{i}} p_{i}^{j} . x_{ih}^{j} \leq l_{t} . y_{th} for all \\ t = 1, 2, \dots T and h = 1, 2, \dots H \end{matrix}

(5)

\begin{array}{l} {}_{i h}^{j}\in {0, 1} for all i = 1, 2, \dots I, j = 1, 2 \dots, J_{i} \\ and h = 1, 2, \dots H \end{array}

(6)

y_{th} \geq 0 and integer for all t = 1, 2, \dots T and h = 1, 2, \dots H

(7)

The objective represents the sum of part processing, earliness/tardiness, tool and subcontracting costs over the planning horizon. Constraint set (1) ensures that each part is selected within the planning horizon or subcontracted, together with determining its processing time. Constraint sets (2) and (3) represent the processing time and the tool magazine capacities, respectively. Also, a constraint set (4) represents the number of available tool copies for each tool type and constraint set (5) represents the tool life restrictions. Finally, the remaining (6) and (7) represent the conditions of decision variables.

It is possible to solve the problem [P] directly using an integer programming software package, but it requires excessive computation time for large sized instances. Note that the problem [P] is NP-hard because it can be reduced to the multi-period part selection problem of Lee and Kim³³ by fixing part processing times and relaxing the tooling constraints (4) and (5) while removing the part processing and tool costs in the objective function. Formally, let $x_{ih}$ = 1 if part $i$ with processing time $p_{i}^{j_{i}}$ is assigned to period $h$ , and 0 otherwise. Also, let $v_{i}$ denote the number of tool slots required by the tools to process part $i$ . Then, the relaxed problem can be represented as follows.

\begin{matrix} [RP] Minimize \sum_{i = 1}^{I} \sum_{h = 1}^{H} (α_{i}^{j_{i}} . x_{ih}) \\ + \sum_{i = 1}^{I} \sum_{h = 1}^{H} (β_{ih} . x_{ih}) + \sum_{i = 1}^{I} \\ {γ_{i} . (1 - \sum_{h = 1}^{H} x_{ih})} \end{matrix}

subject to

\sum_{h = 1}^{H} x_{i h} \leq 1 for all i = 1, 2, \dots I

(1’)

\sum_{i = 1}^{I} p_{i}^{j_{i}} . x_{i h} \leq Q_{h} for all h = 1, 2, \dots H

(2’)

\sum_{i = 1}^{I} v_{i} \cdot x_{i h} \leq M_{h} for all h = 1, 2, \dots H

(3’)

x_{ih} \in {0, 1} for all i = 1, 2, \dots I and h = 1, 2, \dots H

(6’)

Lee and Kim³³ show that the problem [RP] can be transformed into the generalized assignment problem with additional constraints and it can be seen that the problem [P] considered in this study is NP-hard because the special case [RP] is proved to be NP-hard. Therefore, instead of the optimal solution approach with limited applications, the heuristic approach is adopted in this study.

Solution algorithms

This section presents two types of solution algorithms: fast heuristics that can be used when computation time is critical and variable neighborhood search algorithms when solution quality is important.

Fast heuristics

The fast heuristics consist of two stages: (a) obtaining an initial solution; and (b) improvement. Figure 3 shows an overview of the fast heuristics.

Figure 3.

Fast heuristics: overview.

Stage I: Obtaining an initial solution

After the processing time of each part is fixed to its longest one, an initial solution is obtained by a greedy algorithm that sorts the parts in the non-increasing order of subcontracting costs and according to the sorted list, they are assigned to the period with the smallest earliness/tardiness cost without violating the constraints. The detailed procedure is given below. Ties are broken arbitrarily.

Step 1. Sort the parts in the non-increasing order of subcontracting costs $γ_{i}$ .

Step 2. Set the processing time of each part to its longest available one, that is, $p_{i}^{J_{i}}$ for all $i$ .

Step 3. From the first to the last part in the sorted list, find the period $t^{*}$ with the smallest earliness/tardiness cost to which the part can be assigned without violating the constraints. If period $t^{*}$ does not exist, subcontract it. Otherwise, assign it to period $t^{*}$ .

Stage II: Improvement

The initial solution is improved by three consecutive steps: insertion/interchange for early/tardy parts, perturbation for the parts assigned to their due-date periods and reallocation/swapping for subcontracted parts. The details are explained below.

Step 1. Insertion/interchange for early/tardy parts

Let $P_{T}$ and $P_{E}$ denote the sets of tardy and early parts in the current solution, that is,

\begin{matrix} P_{T} = {i | d_{i} < h_{i} \leq H for all i = 1, 2, \dots P} and \\ P_{E} = {i | 1 \leq h_{i} < d_{i} for all i = 1, 2, \dots P}, \end{matrix}

where $h_{i}$ is the period to which part $i$ is assigned in the current solution. Note that $h_{i} = H + 1$ if part $i$ is subcontracted.

Insertion

The insertion method improves the current solution by removing a part in each of $P_{T}$ and $P_{E}$ from its original period and inserting it to other periods that reduces the total cost until no more improvement can be obtained. Specifically, the parts in $P_{T}$ and $P_{E}$ are sorted in the non-increasing order of their earliness/tardiness costs, that is, $β_{i, h (i)}$ , where $h (i)$ denotes the period to which part $i$ is assigned in the current solution. Then, from the first to the last part in the sorted list, it is inserted to other period that improves the current solution. Note that the insertion periods are limited to those with lower earliness/tardiness costs than that of part $i'$ to be inserted, that is, $h' \in R_{i'}$ , where

R_{i'} = {h | β_{i' h} \leq β_{i', h (i')} for all h \neq h (i')} .

In the insertion method, the following methods are tested to select a neighborhood solution.

BI (best improvement): insert the part to the best feasible period that improves the current solution

HI (hybrid improvement): insert the current part to the better one of the first and the best feasible periods that improve the current solution

For the two methods, the neighborhood solutions for each part are generated as follows. Let $X_{h}$ denote the set of parts assigned to period $h$ , that is, $X_{h} = {i | x_{ih}^{j (i)} = 1 for all i}$ , where $j (i)$ denotes the index for the current processing time of part $i$ .

Case 1: If the current part $i'$ with processing time $p_{i}^{j (i)}$ can be assigned to other period $h'$ while improving the current solution without violating the constraints, generate a neighborhood solution by inserting part $i'$ to the period $h'$ without adjusting processing times.

Case 2: Otherwise, generate other neighborhoods that can improve the current solution without violating the constraints by inserting part $i'$ to period $h'$ after adjusting processing times of relevant parts: part $i'$ and parts in $X_{h'}$ .

In the case of part $i'$ , generate a neighborhood solution if it can be inserted to period $h'$ after its processing time is reduced.

In the case of parts in $X_{h'}$ , generate a neighborhood solution if part $i'$ can be inserted to period $h'$ after adjusting the processing times of a part in $X_{h'}$ . In this case, it is needed to select part $i^{*}$ whose processing time is reduced. For this purpose, the following rules are proposed. Note that the parts are selected repeatedly until the first feasible solution is obtained.

MCI (minimum cost increase): select part $i^{*}$ such that

i^{*} = argmi n_{i \in X_{h'}} {α_{i}^{j (i) - 1} - α_{i}^{j (i)}}

MTD (maximum time decrease): select part $i^{*}$ such that

i^{*} = argma x_{i \in X_{h'}} {p_{i}^{j (i)} - p_{i}^{j (i) - 1}}

CTR (cost/time ratio): select part $i^{*}$ such that

i^{*} = argmi n_{i \in X_{h'}} {(α_{i}^{j (i) - 1} - α_{i}^{j (i)}) / (p_{i}^{j (i)} - p_{i}^{j (i) - 1})}

To illustrate the insertion method, consider a 5-period example for five parts each of which has three available processing times. The data are summarized in Table 1.

Table 1.

Insertion method: example.

	Part ( $i$ )
	1	2	3	4	5
Available processing times/costs ( $p_{i}^{j}$ / $α_{i}^{j}$ )	120/90	110/95	130/85	100/100	140/80
	150/75	140/80	160/70	130/85	170/65
	180/60	170/65	200/55	160/70	190/50
Due-dates ( $d_{i}$ )	2	3	3	2	2
Per-period early/tardy costs ( $ϵ_{i}$ / $τ_{i}$ )	6/7	5/8	7/9	7/10	5/7

Let the current solution be

\begin{matrix} x_{11}^{3} = x_{24}^{3} = x_{32}^{3} = x_{45}^{3} = x_{53}^{3} = 1 \\ and x_{ih}^{j} = 0 for the others, \end{matrix}

that is, $P_{T} = {2, 4, 5}$ and $P_{E} = {1, 3}$ . Then, part 4 is selected first for checking improvement because the current earliness/tardiness costs of parts 1, 2, 3, 4, and 5 are 6, 8, 7, 30, and 7, respectively. Now, we can obtain the earliness or tardiness costs incurred when part 4 is assigned to periods 1, 2, 3, and 4, that is,

β_{41} = 7, β_{42} = 0, β_{43} = 10, and β_{44} = 20,

and then it can be reallocated to periods 1, 2, 3, and 4 if all the constraints are satisfied. Among them, consider the case that it is reallocated to period 2. If the reallocation is feasible and improves the current solution, we obtain a neighborhood solution (Case 1). Otherwise, another neighborhood solution can be obtained if an improved feasible solution can be obtained by changing its processing time (Case 2(a)), for example, from $p_{4}^{3} = 160$ to $p_{4}^{2} = 130$ . If an improved one cannot be obtained when its processing time is changed to the smallest one, that is, $p_{4}^{1} = 100$ , the processing time of part 3 already assigned to period 2 is changed to obtain other improved one (Case 2(b)). Recall that the MCT, MTD or CTR rules are used to select a part to reduce its processing time in case that there are two or more parts already assigned to period 2 in the current solution. If no improved feasible solution can be obtained in this way, the period with the next earliness or tardiness is considered for obtaining other neighborhood solution. Finally, the BI and HI methods are used to select one of the neighborhood solutions for each part.

Interchange

After the insertion is done, the current solution is improved further by interchanging early and tardy parts while adjusting the part processing times. Specifically, the parts in $P_{T}$ in the current solution are sorted in the non-increasing order of tardiness costs and then, the best one is selected that improves the current solution among those obtained by interchanging the current part in the sorted list and the parts in the feasible early periods with less earliness costs while adjusting the processing times of the interchanging parts and the other parts already assigned to the two periods with the parts to be interchanged. Similarly, the parts in $P_{E}$ in the current solution are sorted in the non-increasing order of early costs and then, the best one is selected that improves the current solution by interchanging the current part in the sorted list and the parts in the feasible tardy periods with less tardy costs while adjusting the processing times. As in the insertion method, the interchanges are repeatedly done until no more improvement can be obtained.

Step 2. Perturbation for parts assigned to their due-date periods

The perturbation step is done for the parts assigned to their due-date periods. Let $P_{D}^{d_{i}}$ denote the set of parts assigned to the due-date period $d_{i}$ that is, $P_{D}^{d_{i}} = {i | h_{i} = d_{i} for all i = 1, 2, \dots I}$ . Recall that $h_{i}$ denotes the period to which part $i$ is assigned in the current solution.

The perturbation is done from the first to the last due-date period, that is, from $t = 1$ to $T$ . First, the set of parts assigned to the due-date period $t$ is identified. Then, from the smallest to the largest indexed part in $P_{D}^{t}$ , the current part is interchanged with the parts assigned to other periods before or after the due-date period in the non-increasing order of earliness/tardiness costs while adjusting the processing times of the relevant parts, that is, the current part and the parts assigned to the period to which the current part is assigned, using the methods explained earlier while checking the feasibility. If the solution is improved, the current solution is updated and the perturbation is repeatedly done for the remaining parts in $P_{D}^{t}$ .

The detailed perturbation procedure is given below. Ties are broken arbitrarily.

Set $t = 1$ .

Find the set $P_{D}^{t}$ of parts assigned to due-date period $t$ .

From the smallest to the largest indexed part in $P_{D}^{t}$ , do:

Check if the solution can be improved by interchanging the current part and the parts assigned to other periods in the non-increasing order of their earliness/tardiness costs while adjusting the processing times of the current part and the parts assigned to the period to which the current part is assigned.

If an improved solution is obtained, update the solution. Set the current part to the next indexed one and go to Step 3(a).

If $t > T$ , stop. Otherwise, set $t = t + 1$ and go to Step 2.

Step 3. Reallocation/swapping for subcontracted parts

In the reallocation method, the current solution is improved by sorting the subcontracted parts in the non-increasing order of subcontracting costs and then reallocating each part to the first feasible period among those in the non-decreasing order of earliness/tardiness costs while adjusting the processing times of relevant parts explained earlier. After the reallocations, the swapping method improves the current solution by interchanging the remaining subcontracted parts in the non-increasing order of subcontracting costs and the non-subcontracted parts in the non-increasing order of earliness/tardiness costs while adjusting the processing times of the relevant parts.

Variable neighborhood search algorithms

This section explains the variable neighborhood search (VNS) algorithms to improve the fast heuristics. The VNS algorithm, one of well-known meta-heuristics that have been applied to various optimization problems, is based on the systematic change of neighborhood solution within a local search algorithm for the purpose of escaping from local optimums. See Hansen and Mladenović⁴⁰ and Hansen et al.⁴¹ for details on the basic VNS and its variants.

The VNS algorithms proposed in this study consists of four steps: (a) obtaining an initial solution; (b) shaking that generates neighborhood solutions and selects one of them; (c) local search that improves the selected neighborhood solution; and (d) termination. Figure 4 shows an overview of the VNS algorithms. As can be seen in the figure, the shaking and local search improvement steps are repeatedly done until the termination condition is satisfied and the algorithms are terminated when the iteration count reaches a predetermined limit $N$ .

Figure 4.

Variable neighborhood search algorithms: overview.

A solution is represented by a $| P | \times 2$ matrix $Z = (z_{ij})$ , where $z_{i 1}$ and $z_{i 2}$ denote the period to which part $i$ is assigned, that is, 1, 2, … or $H$ , and the index of the available processing time selected by part $i$ , that is, 1, 2, … or $J_{i}$ . Note that $z_{i 1}$ is set to $H + 1$ if part $i$ is subcontracted. Also, the number of tool copies for each tool type in each period is set using the solution $Z$ . Formally,

y_{th} = ⌈ \frac{l_{t}}{\sum_{i \in Φ_{t}} \sum_{j = 1}^{J_{i}} p_{i}^{j} . x_{ih}^{j}} ⌉,

where ⌈·⌉ denotes the smallest integer that is greater than or equal to · and $x_{ih}^{j}$ can be obtained using the solution $Z$ .

Obtaining an initial solution

An initial solution is obtained using the greedy algorithm used by the fast heuristics, that is, parts are sorted in the non-increasing order of subcontracting costs and according to the sorted list, they are assigned to the period with the smallest earliness/tardiness cost without violating the constraints.

Shaking

The shaking is done to resolve any local optima traps by changing neighborhood solutions in a systematic way. As in the ordinary VNS algorithm, the shaking step consists of two parts: (a) generating neighborhood solutions; and (b) selecting one of them. The neighborhood solutions are generated using the interchange method explained earlier, that is, interchanges of early and tardy parts while adjusting the processing times. After the neighborhoods are generated, the selection is done randomly to avoid cycling that may occur if a deterministic rule is used, that is, random jump. Note that three VNS algorithms are tested according to the three processing time adjustment methods in the neighborhood generation, that is, MCI, MTD and CTR.

Local search improvement

This step improves the neighborhood solution selected in the shaking step. For this purpose, the three improvement methods of the fast heuristic approach are sequentially used, that is, insertion/interchange for early/tardy parts, perturbation or the parts assigned to their due-date periods and reallocation/swapping for subcontracted parts.

Computational results

This section presents the test results for the two types of solution algorithms. The algorithms were coded in C and the tests were conducted using a PC with Intel Core i7 CPU at 3.40GHz with 8GB RAM memory.

The first test was done to compare the 6 fast heuristics, that is, six combinations of two insertion/interchange methods (BI and HI) and three processing time adjustment methods in the neighborhood generation (MCI, MTD and CTR). The performance measures to evaluate the results are: (a) percentage gaps from the optimal solution values for small sized test instances, defined for a test instance as

100 \cdot (C_{a} - C_{opt}) / C_{opt},

where $C_{a}$ is the solution value obtained from fast heuristic $a$ and $C_{opt}$ is the optimal value obtained from the CPLEX 12.6 within 1 h; (b) relative performance ratios for medium-to-large sized test instances, defined for a test instance as

(100 \cdot (C_{a} - C_{best}) / C_{best},

where $C_{best}$ is the best solution value among those obtained from all the fast heuristics; and (c) CPU seconds.

For the experiment on small sized instances, we generated 60 instances with 5 periods randomly, that is, 10 instances for each of six combinations of three levels for the number of parts (20, 30, and 50) and two levels of the number of tool types ( $DU (15, 20)$ for high and $DU (10, 15)$ for low), where $DU (a, b)$ denotes the discrete uniform distribution with range $[a, b]$ . The detailed data were generated as follows.

Number of available processing times $(J_{i})$ ∼ $DU (3, 5)$

Processing times $(p_{i}^{j})$ ∼ $U (120, 300)$

Due-dates $(d_{i})$ ∼ $DU (1, H)$

Processing costs $(α_{i}^{j})$ ∼ $DU (100, 200)$

Per-period earliness and tardiness costs $(ϵ_{i}$ and $τ_{i})$ ∼ $U (20, 30)$ and $DU (30, 50)$

Tool cost ( $θ_{t}$ ) ∼ $DU (5, 10)$

Subcontracting costs = $[ma x_{h} {β_{ih}} + α_{i}^{1} + TT C_{i}] \cdot δ$ , where $TT C_{i}$ is the total tool cost of part $i$ , that is, sum of the costs of the tools required to process part $i$ and $δ$ was set to 0.2 with preliminary tests

Number of available tool copies $(f_{t})$ ∼ $DU (5, 10)$

Tool life $(l_{t})$ ∼ $DU (400, 600)$

Set of parts that require a tool type ( $Φ_{t}$ ) ∼ $DU (0, P)$

Number of slots required for each tool type $(s_{t})$ ∼ $DU (3, 5)$

Aggregated processing time capacities ( $Q_{h}$ ) = 600

Aggregated tool magazine capacities ( $M_{h}$ ) = 150

Test results for the small sized instances are given in Table 2 that shows the number of instances that the CPLEX gave optimal solutions within 1 h, CPU seconds of the CPLEX and the average percentage gaps of the 6 fast heuristics. Note that the CPU seconds are not reported because the fast heuristics solved all the test instances within 3 s. It can be seen from the table that the CPLEX could not always give the optimal solutions for the small sized test instances with 30 and 50 parts. In fact, it was found from additional experiments that the CPLEX could not give the optimal solutions for the test instances with 10 and 15 periods within 3600 s. Also, Table 2 shows that all the fast heuristics gave near optimal solutions within 2% gaps although no one dominates the others.

Table 2.

Test results for fast heuristics: small sized test instances.

Number of parts	Number of periods	Number of tool types	CPLEX	Fast heuristics
			N_opt^a/CPU_opt^b	MCI		MTD		CTR
			N_opt^a/CPU_opt^b	BI	HI	BI	HI	BI	HI
20	5	High	10/602.2	4.37^*	4.49	4.00	4.35	3.80	3.53
20		Low	10/28.9	2.56	2.56	2.84	2.84	3.70	3.70
30	5	High	8/162.1	1.45	1.45	1.04	1.26	1.06	1.14
30		Low	10/81.6	1.26	1.26	1.37	1.37	0.87	0.83
50	5	High	8/1206.5	0.75	0.69	0.59	0.59	0.65	0.75
50		Low	9/963.0	0.78	0.78	1.10	1.11	1.06	0.84
Average				1.86	1.87	1.82	1.92	1.86	1.80

Number of instances that CPLEX 12.6 gave the optimal solutions within 3600 s (out of 10 instances).

Average CPU second of CPLEX 12.6 for the instances that the optimal solutions were obtained within 3600 s.

Average percentage gap from the optimal solutions for the instances that the CPLEX gave the optimal solutions.

For the experiment on medium-to-large sized instances, we generated 240 additional instances randomly, that is, 10 instances for each of 24 combinations of four levels for the number of parts (20, 30, 50, and 100), two levels for the number of periods (10 and 15) and two levels of the number of tool types (high and low). The data were generated using the method explained earlier.

Table 3 shows the average relative performance ratios of the 6 fast heuristics. The CPU seconds are not reported because they solved all the test instances within 20 s. It can be seen from the table that the fast heuristics with CTR are better than the others. This is because CTR considers both costs and processing times when adjusting part processing times in the neighborhood generation method. Note that MCI and MTD consider only one factor, that is, cost or processing time. However, as in the results for small sized instances, there is no significant difference between BI and HI. Also, to show the effects of the numbers of parts, periods and tool types and the combinations of insertion/interchange and processing time adjustment methods on the solutions, an analysis of variance (ANOVA) was done using the relative performance ratio values for all test instances and the result given in Table 4 shows that the solutions are significantly affected by the insertion/interchange and processing time adjustment methods. This implies that the two decisions are important ones that must be made efficiently in the FMS part selection.

Table 3.

Test results for fast heuristics: medium-to-large sized test instances.

(a) Relative performance ratios.

Number of parts	Number of periods	Number of tool types	Fast heuristics
			MCI		MTD		CTR
			BI	HI	BI	HI	BI	HI
20	10	High	2.46^*	2.46	2.08	2.08	1.73	1.39
	10	Low	2.96	2.54	3.07	3.18	0.85	0.85
	15	High	2.98	3.18	4.55	4.55	2.85	2.85
	15	Low	3.76	3.76	0.48	0.48	1.92	1.92
30	10	High	1.94	1.18	3.19	3.19	2.49	2.44
	10	Low	2.96	2.54	3.07	3.18	0.85	0.85
	15	High	2.98	3.18	4.55	4.55	2.85	2.85
	15	Low	3.76	3.76	0.48	0.48	1.92	1.92
50	10	High	2.85	2.85	0.82	0.85	1.33	1.33
	10	Low	0.78	0.78	1.58	1.49	1.18	1.10
	15	High	2.14	2.14	1.26	1.90	1.43	1.68
	15	Low	1.80	1.80	2.56	2.22	1.81	1.77
100	10	High	1.13	1.14	0.63	0.44	0.55	0.38
	10	Low	0.56	0.69	0.30	0.30	0.51	0.50
	15	High	1.78	1.70	0.74	0.74	0.57	0.57
	15	Low	0.62	0.74	0.86	0.86	1.03	1.03
Average			2.22	2.15	1.89	1.90	1.49	1.46

Average relative performance ratio out of 10 instances.

(b) CPU seconds.

Number of parts	Number of periods	Number of tool types	Fast heuristics
			MCI		MTD		CTR
			BI	HI	BI	HI	BI	HI
20	10	High	0.9^*	1.3	1.0	1.3	0.9	1.3
	10	Low	1.2	1.7	1.4	1.8	1.1	1.7
	15	High	0.9	1.3	1.0	1.3	0.8	1.4
	15	Low	1.2	1.7	1.3	1.7	1.1	1.7
30	10	High	2.2	2.5	2.3	2.6	2.2	2.7
	10	Low	2.4	2.8	2.7	2.8	2.6	2.9
	15	High	2.6	3.1	2.7	3.1	2.5	2.8
	15	Low	2.8	3.6	2.8	3.3	2.8	3.1
50	10	High	4.7	5.5	5.3	5.8	4.9	5.4
	10	Low	5.6	6.0	5.1	5.6	5.0	5.6
	15	High	5.9	7.0	5.9	6.8	5.8	6.3
	15	Low	6.7	7.8	7.1	8.1	7.4	8.4
100	10	High	18.9	24.9	15.1	26.8	21.2	24.0
	10	Low	18.6	21.7	16.0	15.3	18.5	18.9
	15	High	15.4	17.9	15.1	19.9	19.1	20.8
	15	Low	15.3	17.9	13.1	16.9	14.4	16.3

Average CPU second out of 10 instances.

Table 4.

Analysis of variance for the effects of four factors.

Source of variation	Sum of squares	Degrees of freedom	Mean squares	F values
NP^a	821.936	3	273.979	619.407^**
NPR^b	208.021	1	208.021	470.291^**
NT^c	0.187	1	0.187	0.422
Methods^d	765.884	11	69.626	157.409^**
Error	42.021	95	0.442
Total	6128.991	192

Number of parts.

Number of periods.

Number of tool types.

Combinations of insertion/interchange and processing time adjustment methods.

There is difference in the effects at a significance level of 0.01.

The last experiment was done to test the VNS algorithms with different processing time adjustment methods (MCI, MTD and CTR), where the algorithms were terminated when the iteration count ( $N$ ) reaches 100. The first results are summarized in Table 5(a) that shows the average percentage gaps from optimal solution values for the small sized test instances. It can be seen that the the VNS-CTR&HI outperforms the others with 0.82% in an overall average. Also, Table 5(b) summarizes the percentage improvement over the best one among those obtained by the 6 fast heuristics and CPU seconds for all the test instances, where the HI method was used in the local search improvement step according to the test results for the fast heuristics,. It can be seen from the table that the VNS algorithms improve the fast heuristics significantly, that is, 2.66%, 2.61%, and 2.24% in overall averages for VNS-CTR, VNS-MCI, and VNS-MTD, respectively. To test statistical difference among the performance of the VNS algorithms, paired t-tests were done using the relative performance ratio values and the results given in Table 6 that shows the VNS-CTR outperforms the others statistically. Finally, the VNS algorithms required longer CPU seconds than the fast heuristics due to their larger search space. Nevertheless, they gave the solutions for all the test instances within 2 min.

Table 5.

Test results for VNS algorithms.

(a) Average percentage gaps.

Number of parts	Number of periods	Number of tool types	VNS algorithms
			MCI		MTD		CTR
			BI	HI	BI	HI	BI	HI
20	5	High	1.72^**	1.57	1.72	1.61	1.39	1.29
20	5	Low	1.46	1.54	1.38	1.15	1.52	1.00
30	5	High	1.00	0.64	0.98	0.67	0.88	0.96
30	5	Low	0.89	0.83	0.74	0.80	0.87	0.80
50	5	High	0.56	0.56	0.49	0.56	0.41	0.41
50	5	Low	0.68	0.68	0.72	0.68	0.81	0.58
Average			1.05	0.97	1.03	0.93	0.95	0.82

Average percentage gap from the optimal solution values for the instances that the CPLEX gave the optimal solutions.

(b) Percentage improvement over fast heuristics.

Number of parts	Number of periods	Number of tool types	VNS algorithms
			MCI		MTD		CTR
			PI^*	CPU^**	PI	CPU	PI	CPU
20	5	High	1.19	4.1	3.16	5.2	2.61	4.6
	5	Low	2.90	4.8	2.49	4.8	2.00	4.5
	10	High	3.59	8.7	3.08	8.0	4.14	10.7
	10	Low	2.50	14.0	3.13	14.7	3.55	16.2
	15	High	7.10	12.4	6.45	7.8	6.71	14.9
	15	Low	5.12	13.5	6.20	13.6	6.95	13.8
30	5	High	0.24	6.1	0.58	6.9	0.16	6.7
	5	Low	0.23	6.6	0.20	6.7	0.02	6.6
	10	High	2.63	11.1	4.05	10.7	3.49	12.5
	10	Low	2.17	10.1	5.03	9.1	3.87	12.9
	15	High	4.16	16.4	6.97	15.8	6.82	19.4
	15	Low	3.52	18.5	4.07	19.6	3.86	17.6
50	5	High	0.23	5.4	0.63	6.1	0.32	3.1
	5	Low	0.16	10.8	0.10	11.1	0.26	4.5
	10	High	2.47	19.4	2.26	32.0	3.10	26.5
	10	Low	3.04	15.5	1.63	31.5	2.63	21.2
	15	High	2.52	27.0	2.34	32.9	2.78	27.9
	15	Low	1.95	28.6	1.46	35.6	1.86	27.2
100	5	High	0.48	11.4	1.32	12.8	0.67	6.4
	5	Low	0.34	22.7	0.21	23.3	0.55	9.4
	10	High	2.31	70.4	1.96	45.0	2.01	75.4
	10	Low	1.75	60.0	1.51	59.5	1.72	64.8
	15	High	2.16	47.0	2.10	80.0	2.60	66.9
	15	Low	1.03	33.9	1.59	56.4	1.20	42.8
Average			2.24		2.61		2.66

Average percentage improvement over the best one among those obtained by the 6 fast heuristics.

Average CPU second out of 10 instances.

Table 6.

Results of the paired t-tests for VNS algorithms.

Algorithms (ARPR†)	VNS-CTR	VNS-MCI
VNS-CTR (2.03)
VNS-MCI (2.42)	**
VNS-MTD (2.58)	**	=

†

Average relative performance ratio.

Statistically different at a significant level of 0.05.

=Statistically indifferent at a significant level of 0.05.

Concluding remarks

This study considered a multi-period part selection problem for FMSs in which part processing times are controllable to optimize energy consumption, part precision levels, operational performances, and so on. Tool sharing among different part types is also considered to obtain practically feasible solutions applicable to real FMSs. The problem is to determine the set of parts to be produced in each period, part processing times and the number of copies for each tool type while satisfying the processing time capacity, tool magazine capacity and tool life constraints. The objective is to minimize the sum of part processing, earliness/tardiness, tool and subcontracting costs. After an integer programming model was proposed, together with proving its NP-hardness, two types of heuristics were proposed: fast heuristics useful when computation time is critical and variable neighborhood search algorithms useful when solution quality is important. Computational experiments were done on various test instances and the results are as follows. First, among the 6 fast heuristics, the ones with the CTR (cost/time ratio) based processing time adjustment method work better than the other, and gave near optimal solutions for small sized test instances, that is, within 2% from the optimal solution values in the overall average. Second, the VNS algorithms improve the fast heuristics significantly, that is, 2.66%, 2.61%, and 2.24% for VNS-CTR, VNS-MCI, and VNS-MTD, respectively. Finally, as in the test results of the fast heuristics, VNS-CTR performs the best.

This study can be extended as follows. First, the problem can be extended to stochastic ones with uncertain processing times, costs, machine/tool breakdowns, and so on. Second, it is needed to integrate the part selection model with other FMS operation problems such as machine loading and scheduling.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the Technology Innovation Program funded by the Ministry of Trade, Industry & Energy, Korea Government. (Grant code: 10052978-2015-4, Title: Development of a jig-center class 5-axis horizontal machining system capable of over 24 hours continuous operation)

ORCID iD

Dong-Ho Lee

References

Koren

Heidel

Jovane

, et al. Reconfigurable manufacturing systems. CIRP Ann 1999; 48(2): 527–540.

Lang

Shen

, et al. Reconfigurable manufacturing systems: the state of the art. Int J Prod Res 2008; 46(4): 967–992.

Radziwon

Bilberg

Bogers

, et al. The smart factory: exploring adaptive and flexible manufacturing solutions. Procedia Eng 2014; 69: 1184–1190.

Kang

H-S

Lee

J-Y

Choi

, et al. Smart manufacturing: past research, present findings and future directions. Int J Precis Eng Manuf Green Technol 2016; 3(1): 111–128.

Mittal

Khan

Romero

, et al. Smart manufacturing: characteristics, technologies and enabling factors. Proc IMechE, Part B: J Engineering Manufacture 2019; 233(5): 1342–1361.

Shukla

Tiwari

Beydoun

Next generation smart manufacturing and service systems using big data analytics. Comput Ind Eng 2019; 128: 905–910.

Stecke

. Design, planning, scheduling, and control problems of flexible manufacturing systems. Ann Oper Res 1985; 3(1): 1–12.

Kouvelis

. Design and planning problems in flexible manufacturing systems: A critical review. J Intell Manuf 1992; 3(2): 75–99.

Tempelmeier

Kuhn

. Flexible manufacturing systems: decision support for design and operation. New York: John Wiley & Sons, 1993.

10.

Nowicki

Zdrzałka

. A survey of results for sequencing problems with controllable processing times. Discrete Appl Math 1990; 26(2–3): 271–287.

11.

Arif

Stroud

Akten

. A model to determine the optimal parameters in a machining process for the most profitable utilization of machining energy. Proc IMechE, Part B: J Engineering Manufacture 2014; 229(2): 266-274.

12.

Wang

Liu

Wang

. Multi-objective optimization of machining parameters considering energy consumption. Int J Adv Manuf Technol 2014; 71(5–8): 1133–1142.

13.

Liu

Xie

Liu

. A method for predicting the energy consumption of the main driving system of a machine tool in a machining process. J Clean Prod 2015; 105: 171–177.

14.

Moradnazhad

Unver

. Energy efficiency of machining operations: a review. Proc IMechE, Part B: J Engineering Manufacture 2016; 231(11): 1871–1889.

15.

Zeid

Doh

H-H

Shin

J-H

, et al. Due-date based multi-period part selection for flexible manufacturing systems with controllable processing times. In: Proceedings of IFIP International Conference on Advances in Production Management Systems (APMS 2018), Seoul, Korea, 26–30 August 2018, pp.443–449.

16.

Hwang

S-S

. A constraint-directed method to solve the part selection problem in flexible manufacturing systems planning stage. In: Proceedings of the second ORSA/TIMS conference on flexible manufacturing systems: operations research models and applications, Michigan, USA, 12–15 August 1986, pp.297–309.

17.

Hwan

Shogan

. Modelling and solving an FMS part selection problem. Int J Prod Res 1989; 27(8): 1349–1366.

18.

Srivastava

Chen

. Part type selection problem in flexible manufacturing systems: Tabu search Algorithms. Ann Oper Res 1993; 41(3): 279–297.

19.

Srivastava

Chen

W-H

. Batching in production planning for flexible manufacturing systems. Int J Prod Econ 1996; 43(2–3): 127–137.

20.

Kim

Y-D

Yano

. A due date-based approach to part type selection in flexible manufacturing systems. Int J Prod Res 1994; 32(5): 1027–1043.

21.

Denizel

Sayin

. Part-type selection in flexible manufacturing systems: A bicriteria approach with due dates. J Oper Res Soc 1998; 49(6): 659–669.

22.

Chen

Ker

Kleawpatinon

. An effective part-selection model for production planning of flexible manufacturing systems. Int J Prod Res 1995; 33(10): 2671–2683.

23.

Tabucanon

Batanov

Basu

. Using simulation to evaluate the batching approach to part type selection in flexible manufacturing systems. Integr Manuf Syst 1998; 9(1): 5–14.

24.

Kim

Y-D

Yano

. An iterative approach to system setup problems in flexible manufacturing systems. Int J Flex Manuf Syst 1992; 4(2): 183–209.

25.

Binghai

Lifeng

Yongshang

. A heuristic algorithm to batching and loading problems in a flexible manufacturing system. Int J Adv Manuf Technol 2004; 23(11–12): 903–908.

26.

Arikan

Erol

. A hybrid simulated annealing-tabu search algorithm for the part selection and machine loading problems in flexible manufacturing systems. Int J Adv Manuf Technol 2012; 59(5–8): 669–679.

27.

Arikan

Erol

. Meta-heuristic approaches for part selection and tool allocation in flexible manufacturing systems. Int J Comput Integr Manuf 2006; 19(4): 315–325.

28.

Choudhary

Tiwari

Harding

. Part selection and operation-machine assignment in a flexible manufacturing system environment: a genetic algorithm with Chromosome Differentiation-Based Methodology. Proc IMechE, Part B: J Engineering Manufacture 2006; 220(5): 677–694.

29.

Tiwari

Kumar

Shankar

. Solving part-type selection and operation allocation problems in an FMS: an approach using constraints-based fast simulated annealing algorithm. IEEE Trans Syst Man Cybern A Syst Hum 2006; 36(6): 1170–1184.

30.

Prakash

Khilwani

Tiwari

, et al. Modified immune algorithm for job selection and operation allocation problem in flexible manufacturing systems. Adv Eng Softw 2008; 39(3): 219–232.

31.

Bilge

Albey

Beşikci

, et al. Mathematical models for FMS loading and part type selection with flexible process plans. Eur J Ind Eng 2015; 9(2): 171–194.

32.

Stecke

Toczyłowski

. Profit-based FMS dynamic part type selection over time for mid-term production planning. Eur J Oper Res 1992; 63(1): 54–65.

33.

Lee

D-H

Kim

Y-D

. A multi-period order selection problem in flexible manufacturing systems. J Oper Res Society 1998; 49(3): 278–286.

34.

Rajagopalan

. Formulation and heuristic solutions for parts grouping and tool loading in flexible manufacturing systems. In: Proceedings of the second ORSA/TIMS conference on flexible manufacturing systems: operations research models and applications, Michigan, USA, 12–15 August 1986, pp.312–320.

35.

Lee

D-H

Lim

S-K

Lee

G-C

, et al. Multi-period part selection and loading problems in flexible manufacturing system. Comput Ind Eng 1997; 33(3–4): 541–544.

36.

Lee

D-H

Kim

Y-D

. Iterative procedures for multi-period order selection and loading problems in flexible manufacturing systems. Int J Prod Res 1998; 36(10): 2653–2668.

37.

Albey

Bilge

. A hierarchical approach to FMS planning and control with simulation-based capacity anticipation. Int J Prod Res 2011; 49(11): 3319–3342.

38.

Mahmudy

Mariana

Luong

. Hybrid genetic algorithms for multi-period part type selection and machine loading problems in flexible manufacturing system. In: Proceedings of 2013 IEEE international conference on computational intelligence and cybernetics (CYBERNETICSCOM 2013), Yogyakarta, 2013, Indonesia, pp.126–130.

39.

Shin

J-H

J-M

Doh

H-H

, et al. Batching and scheduling for a single-machine flexible machining cell with multi-fixturing pallets and controllable processing times. Int J Prod Res 2020; 58(3): 863–877.

40.

Hansen

Mladenović

. Variable neighborhood search: Principles and applications. Eur J Oper Res 2001; 130(3): 449–467.

41.

Hansen

Mladenović

Todosijević

, et al. Variable neighborhood search: basics and variants. EURO J Comput Optim 2017; 5(3): 423–454.

Fast and meta heuristics for part selection in flexible manufacturing systems with controllable processing times

Abstract

Keywords

Introduction

Literature review

Problem description

Solution algorithms

Fast heuristics

Stage I: Obtaining an initial solution

Stage II: Improvement

Insertion

Interchange

Variable neighborhood search algorithms

Obtaining an initial solution

Shaking

Local search improvement

Computational results

Concluding remarks

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References