1. INTRODUCTION
RMCs (Reconfigurable Manufacturing Cells) are production systems which can rapidly change hardware configurations to respond to market variance. An RMC consists of loading/unloading (L/U) stations, numerical control (NC) machines (e.g. horizontal machining centers), material handling devices (e.g. automated guided vehicles), and storage rack of pallets. Figure 1 shows the typical RMC in development.
Reconfiguring is rearrangement of equipment among RMCs, to adjust production capacity among product groups. The reconfigurable equipment is L/U stations, NC machines, and pallets. Figure 2 indicates the concept of reconfiguring. Note that the total number of equipment of the whole factory does not change.
Since market demand is changing, the current configuration may not be appropriate to respond to demand. In this case, production managers are concerned with performance improvement of their manufacturing systems through hardware reconfiguration. Figure 3 indicates different manufacturing performance according to configurations. In Figure 3, ‘Configuration 2’ (C2) performs better than ‘Configuration 1’ (C1), since with C2 both cells may finish production within the available time, while production delay may happen in RMC 1 with C1. Although it takes time to change configuration from C1 to C2, as in Figure 3, C2 may satisfy demand on time.
On the other hand, scheduling may be required to evaluate manufacturing performance of a configuration. The required production time of each RMC in Figure 3 was obtained by generating schedules given hardware configuration, as shown in Figure 4.
Schedulinglevel evaluation of hardware configurations provides reliable information for decisionmaking. The schedule specifies detailed resource allocation over time and close to actual production, so it would be reliable to compare configuration alternatives based on their schedules. With schedulinglevel evaluation, therefore, managers may make decisions with certainty.
Studies that provide schedulinglevel resolution in reconfiguration of manufacturing systems are very few. Ye and Liang (2006) proposed an integrated model for scheduling of modular products and reconfiguring of manufacturing cells and suggested a genetic algorithm which determines cell configurations and job sequences simultaneously, but it did not consider capacity scalability. Nan et al. (2007) and Zheng et al. (2010) used the timed petrinet to generate the reconfiguration plan in combination with the corresponding schedule. The petrinet model, however, has limitation that its complexity dramatically increases as does the problem size. The suggested search technique based on the reachability graph was also appropriate for the small problems. Seo and Park (2013) investigated enhanced flexibility of RMCs compared to conventional FMCs using the constraint programming and sought to make integrative decisions for the reconfiguring problem in the scheduling level, but the constraint programming may perform poor especially when the problem size is large, since it is eventually based on the enumeration of the search tree (Soto et al., 2012). Moreover none of research has been conducted to develop a scheduling algorithm in consideration of hardware reconfiguration.
The reason why previous studies on hardware reconfiguration do not provide accurate evaluation of manufacturing performance is that it had taken long time to change hardware configuration. When the concept of RMS (reconfigurable manufacturing system) was introduced in late 1990s, it took one month or more to change hardware configurations. So reconfiguration decisions have been considered as longterm (over a year) decisions (ElMaraghy, 2006; Mehrabi et al., 2000; Spicer and Carlo, 2007; Youssef and ElMaraghy, 2006), as Deif and EIMaraghy (2006) pointed out that “the rate of variation in demand is usually much higher than the rate at which capacity can be changed and reconfiguration decision is tactical rather than operational.” In order to respond to everchanging demand more quickly, development of manufacturing systems with small changeover cost was requested. In response, a Korean governmental research project for the development of RMC (reconfigurable manufacturing cell) was launched in 2009 (Lee et al., 2010). In the manufacturing system with RMCs, reconfiguration happens not throughout the entire factory but within RMCs, and components consisting of RMCs are highly modularized. As a result, time required for reconfiguration has been reduced to few days (The final objective of changeover time in this research project is one day). As shortterm demand forecast is relatively accurate and difference from actual demand is relatively small, schedulinglevel evaluation of RMCs would be meaningful for reliable decisionmaking.
In this context, this study aims to develop a scheduling algorithm for RMCs in consideration of hardware reconfiguration.
The reminder of this paper is as follows. In the next section, relation between hardware reconfiguration and scheduling is further explained, together with scheduling environment and corresponding mathematical model. After that, a scheduling algorithm for hardware reconfiguration is proposed and experiment to verify the performance of the proposed algorithm is conducted. Finally it ends up with conclusion and future research.
2. PROBLEM DESCRIPTION AND MODEL
Figure 5 indicates the overall flow chart for hardware reconfiguration. As input, the hardware configuration of the current system and demand for upcoming periods are given. Information about the current configuration is required, because reconfiguration cost is determined with regard to the current configuration. Then the current configuration is selected at first as an alternative configuration to obtain base performance. After that the selected configuration is evaluated. This is done via scheduling with the selected configuration as explained in Figure 5. If the selected configuration appeared the best configuration so far, related information is updated. And for remaining alternatives, the above selection and evaluation processes are repeated until all possible configurations have been investigated explicitly or implicitly. Finally it ends up with reporting the best configuration.
As shown in Figure 5, scheduling is required every time an alternative configuration is evaluated. As a large number of configurations may exist and need to be evaluated, the scheduling algorithm should generate schedule as fast as possible, otherwise it will take too much time to find the best configuration. On the other hand, the scheduling algorithm should perform consistent for various configurations in order that managers may have confidence with the schedules generated by the scheduling algorithm.
This study is concerned with development of a scheduling algorithm as a basic component for hardware reconfiguration in RMC environment. In the following section, scheduling environment is described.
2.1 Description of the Scheduling Problem
Here we are concerned with the scheduling environment to evaluate a given hardware configuration.
Figure 6 shows a typical layout of a factory in consideration. There exist multiple cells of RMCs in the factory, each for a production line. A production line is made up of dedicated and assembly shops together with an RMC. This shop environment is sometimes called a cellular reconfigurable manufacturing system (RMS) (Yu et al., 2012), or may be named as a multicell RMS according to (MacCarthy and Liu, 1993).
An RMC consists of L/U stations, NC machines and pallets and those components are identical among the same types of components. Therefore an RMC is defined by the number of L/U stations, NC machines and pallets.
And each RMC is given a production order for a predefined demand period (e.g. monthly demand), which is defined by product types and volumes. The partgrouping problem is not concerned and related decisions are assumed given (Soto et al., 2012).
Now let’s see an individual RMC which processes production orders for a configuration period. Each order indicates manufacturing parts of a certain type. Each part is produced through two consequent operations: loading (or setup) and machining. Loading operations are performed in L/U stations and machining operations in NC machines. A loading operation includes removing of the completed part and mounting of a new part on a pallet. After loading, parts may be processed in one of available machines directly or wait in a buffer. Processing times of operations may differ from part types.
For any operation, an empty pallet is required. Every pallet is the same, but distinguished by the fixture installed on it. And the installed fixture determines the supporting part type of the pallet. The palletfixture assignment specifies which fixtures are to be installed on pallets. Figure 7 indicates the example of the palletfixture assignment. The palletfixture assignment is given before production begins. It is assumed that the number of pallets allocated for each part type is not enough to ignore the pallet constraint during production.
After machining, processed parts are extracted from the cell through L/U stations and returns pallets for processing of next parts.
It is assumed that cutting tools are not scarce resource and there exist enough capacity of tool magazine. Therefore the partloading problem or partmix allocation problem (Lee and Kim, 1996) is not considered here. Besides, deterministic operation time is assumed and material handling time and the size of buffers are not considered.
Managerial objective is the maximum completion time or the makespan. It is known that the makespan objective guarantees high resource utilization (Pinedo, 1995). Based on the makespan, managers may estimate the production time of an RMC with the selected configuration.
The makespan is also related to energy cost, since earlier production means less energy consumption (Mashaei and Lennartson (2013) dealt with the onoff control strategy of flexible manufacturing systems with energy cost as the objective function).
2.2 Problem Classification and Related Studies
Liu and MacCarthy (1996) presented a classification scheme of FMS scheduling according to FMS type, capacity constraints, job description, production environment, and scheduling criteria. According to it, the scheduling environment with which this study is concerned is ‘FMC/lim: LU, M, PL/JC1/pr, +pt/C_max’ which means FMS type is FMC which a group of a single flexible machine(SFM)s sharing one common material handling device, with limited (denoted by ‘lim’) number of L/U stations, machines and pallets. And each job consists of just one operation (‘JC1’), and orders are handled periodically (‘pr’), consisting of more than one part per each part type (‘pt’) for makespan objective.
There were some studies which dealt with similar scheduling environment. Rahimifard and Newman (1999) considered simultaneous scheduling of workpieces, fixtures and cutting tools. Seo and Park (2011) discussed about how to improve practicality of FMS schedulers and presented a database structure and Na et al. (2011) investigated the FMC scheduling and rescheduling problems during transient disturbance period, both considering palletfixture assignment. However above studies were conceptual not suggesting any algorithm or methodology for resolution.
ShalevOren and Schweitzer (1985) presented an analytic model based on the mean value analysis to measure performance of FMS according to priority rules considering the palletfixture assignment and material handling time. Solot and Bastos (1988), and Solot (1990) also investigated into the optimal number of pallets for several part types using the queuing network. Queuing networkbased models have an advantage in fast obtaining of steadystate performance, but are limited in that only simple queuing disciplines are applicable and there usually exists an error between estimated performance and actual (or simulated) result. In ShalevOren et al. (1985) the estimated result was compared with the actual and appeared to have difference of around 413% for small size problems.
Denzler et al. (1987) investigated performance of various part loading rules. Yu et al. (2012) divided scheduling decisions into input sequencing, operation/machine selection, and part sequencing and examined performance of various combinations of priority rules. Han et al. (2012) dealt the case where the palletfixture assignment is decidable and tried to improve manufacturing performance in an integrative manner. Sethi et al. (1999) verified performance of GilmoreGomory’s algorithm proposed by Gilmore and Gomory (1964) for scheduling two stage palletconstrained flow shop with a single processor for each stage, and with commonly shared pallets regardless of part types or fixtures. The above studies, however, did not provide sufficient analysis of problems but investigated existing or simple dispatching rules. For developing an efficient scheduling algorithm, thorough analysis of problems is crucial.
In the next section a mathematical model is presented for further problem analysis and algorithm development.
2.3 Mathematical Model
Based on the problem description in section 2.1, following mathematical model is built:
• Input parameters

i : Index of part types

l_{i} : Part i’s loading (or setup) time

m_{i} : Part i’s machining time

q_{i} : Production quantity (or demand) for part i

L : The number of L/U stations

M : The number of NC machines

p_{i} : The number of fixtured pallets which support part type i

T : The upper bound of the maximum completion time

t : Time index (t = 1, 2, …, T)

W : The large number
Both the loading and machining times ( l_{i} and m_{i} ) are assumed to be of integer multiples. The upper bound ( Τ ) of the makespan would be obtained by applying a simple dispatching rule such as SPT.
• Decision variables

${S}_{it}^{\text{l}},\text{\hspace{0.17em}}{S}_{it}^{\text{m}}$ : The number of parts of type i which start its loading or machining operations at time t
• Dependent variables

${C}_{it}^{\text{l}},\text{\hspace{0.17em}}{C}_{it}^{\text{m}}$ : The number of parts of type i which complete its loading or machining operations at time t

${R}_{t}^{\text{l}},\text{\hspace{0.17em}}{R}_{t}^{\text{m}}$ : The number of L/U stations or NC machines which process parts at time t

A_{it} : The number of pallets for type i which are occupied by parts for processing at time t

x_{it} : Binary variable indicating whether there is any part of type i which completes its machining operation at time t (1: exist, 0: not exist).

C_{max} : The maximum completion time or makespan
The expected range of the makespan ( C_{max} ) is from few days to few weeks.
(1)  (3) means every part must start its loading and machining operations and operations should start so that it may finish within the upper time limit. (4), (5) indicates relation between start and completion times of operations, and (6) forces the machining operation to start after the loading operation. (7)  (12) shows occupation of resources – both equipment and pallets – along time and (13), (14) says it should be less than or equal to resource capacity. Through (15), (16) the maximum completion time can be calculated. (17) indicates the variable conditions. Finally (18) indicates the objective function is to minimize the maximum completion time.
The complexity of the problem is NP complete, for it can be reduced to the twostage hybrid flowshop scheduling problem, which is NPcomplete (Gupta, 1988), by allowing enough pallets for each part type. When the problem was formulated in the exact search engine (iLOG CPLEX), the small size problem of around 10 jobs with 5 part types were taken over 1 and half hour, to find an optimal solution. It is practically impossible to apply an analytic approach. Therefore a heuristic approach may be a practical alternative.
From the next section it will be discussed about the development of scheduling algorithm for resolution of the problem.
3. DEVELOPMENT OF SCHEDULING ALGORITHM
In this chapter, the scheduling algorithm is developed based on an analysis of the problem.
3.1 Analysis of the Problem
Before developing a scheduling algorithm, it needs to understand facts around the problem. First, the makespan (z∗) cannot be less than the total work amount allocated to each resource type divided by that resource capacity (or number). It means that the work amounts of various resource types constitute the initial lower bounds of the problem. In the problem are three kinds of resources – L/U stations, NC machines, and pallets, and each constitutes an initial lower bound. In detail, they are given like below:
3.1.1 The Lower Bound in L/U Station Bottleneck Case
The superscript 0 in variable name means it is the initial lower bound calculated before the schedule is generated (i.e. no decision is made).
3.1.2 The Lower Bound in NC Machine Bottleneck Case
The lower bound for pallet bottleneck case is a little bit different from the other cases. Because pallets are distinguished by their supporting part types, the lower boundshould be calculated for each of part types. Lower bound of pallets for part type k is given like that:
Finally the palletbased lower bound is like below:
3.1.3 The Lower Bound in Pallet Bottleneck Case
Definitely, ${\text{z}}^{\text{*}}\ge \underset{i}{\text{max}}L{B}_{i}^{0}.$ This information of lower bounds may be used as an estimator for ${z}^{\text{*}}.$
Each $L{B}_{i}^{0}$ assumes no or minimum idleness of resources. But as a schedule is generated, resource idleness may occur. This is when there is no waiting job or workin process (WIP) in the queue, while resource is available. The resource idleness increases the corresponding $L{B}_{i}^{t}$ and may increase the $\mathrm{max}L{B}_{i}^{t},$ according to whether the idle resource is bottleneck (Superscript t in $L{B}_{i}^{t}$ means the lower bound updated with regard to the schedule generated by time t.). Figure 8 indicates impact of resource idleness on remaining work amount (WKR) and the updated lower bound. During the resource idle period, $\text{a}\le t\le b$ where WIP = 0, remaining work amount is stagnant and it may lead to the increase of the lower bound.
On the other hand, as the second fact, job allocation decisions affect the future state of the system, especially WIP. The impact of decisions on the future status is predictable via projection. For example, as in Figure 9 , if a loading operation of part type i is assigned to a L/U station at t = c, then after the loading time (l_{i}), at t = b = c + l_{i} , the amount of WIP waiting for machining operations increases as much as the machining time (m_{i}). Conversely, if a machining operation of part type i is allocated to a NC machine, then after the machining time (m_{i}), the amount of WIP waiting for loading operations may increases, since the corresponding pallet is released for the next part, if exists. Through this WIP projection, the remaining work amount and the lower bound in the future time are also predictable.
Another implication of this second fact is that: It may not be enough to consider only permutation schedules. In two stage (flexible) flowshop, it is known that there always exists an optimal schedule where the job sequence in both stages is identical (i.e. a permutation schedule) (Baker, 1974). In the pallet constraint flowshop, however, this property does not always stands.
Property In palletconstraint flowshops, where different pallets are required for different part types, permutation schedules may not constitute a dominant set.
Proof See the counter example in the Appendix.
This property comes from the fact that the decisions in the second stage affect the future decisions in the first stage, since pallets circulate between stages.
Combining the two facts discussed above, it may be concluded that: During the schedule generation process, job allocation decisions affect WIP of resources in the future time, resulting in the probable increase of the lower bound with respect to that time point. A good schedule may be obtained, if decisions are made so that the increment from the initial lower bound ($\underset{i}{\text{max}}L{B}_{i}^{0}$ ) is as small as possible. This philosophy led us to the algorithm which will be described in the next section.
3.2 Description of the Scheduling Algorithm
The developed scheduling algorithm takes dispatching approach where a partial schedule is generated at every decision point (i.e. when a resource becomes available) in chronological order and generation of the entire schedule is completed when all operations are assigned according to production requirement.
Algorithm Whenever a resource becomes available, allocate an operation such that its allocation will result in the minimum projected lower bound in the future. Detailed steps are as follows:
• Step 1 : Initialization
Initialize the partial schedule (S) as an empty schedule. Set the projection time (τ) to 0. Go to step 2.
• Step 2 : Dispatching
Based on S, find the minimum time t when equipment (L/U station or NC machine) becomes available.

(2.1) Find operations assignable to that equipment. Set those operations as J.

(2.2) For each operation j∈ J , calculate the projected lower bound $(\underset{k}{\text{max}}L{B}_{k}^{{\tau}^{\prime}}(j))$ for the future time $\tau \prime =\mathrm{max}\{\tau ,t+{l}_{j}^{k}(\text{or}\hspace{0.17em}{m}_{j})\}$

(2.3) Assign an operation $p=\text{arg}\underset{j\in J}{\mathrm{min}}\{\underset{k}{\text{max}}L{B}_{k}^{{\tau}^{\prime}}(j)\}$ to available equipment. If tie happens, assign the operation with larger τ ′.

(2.4) Set τ = max{τ, τ′} and go to step 3.
• Step 3 : Termination
Terminate if all operations are assigned. Output S as the final schedule. Otherwise go to step 2.
$L{B}_{k}^{{\tau}^{\prime}}(j)$ is the projected lower bound of k^{th} type for time τ′, if part j ∈ J is assigned to available equipment at the decision point, based on decisions made so far. Detail information is given below:
Where

${u}_{k}^{l}(j,\tau ),\hspace{0.17em}{u}_{k}^{m}(j,\tau ):$ Binary variable indicating whether there would exist an operation in processing at a L/U station or NC machine k at time τ , if part j is assigned at the current decision point (1: exist, 0: nonexists).

${r}_{k}^{l}(j,\hspace{0.17em}\tau ),\hspace{0.17em}{r}_{k}^{m}(j,\hspace{0.17em}\tau ):$ Projected remaining operation time of a L/U station or NC machine k with respect to time τ , if an operation j is assigned at the current decision point.

${q}_{i}^{l}(j,\hspace{0.17em}\tau ),\hspace{0.17em}\hspace{0.17em}{q}_{i}^{m}(j,\hspace{0.17em}\tau ):$ Projected remaining quantity of loading operations or machining operations with respect to time τ , if an operation j is assigned at the current decision point.

F(k) : Part index of an operation which is being processed in a L/U station or NC machine k.
In calculation of $L{B}_{k}^{{\tau}^{\prime}}(j),$ $L{B}_{k}^{0}$ is extended so that it would reflect the future system status which is derived by workinprocess projection, explained in Figure 8 and Figure 9.
3.3 Example for the Proposed Algorithm
For better understanding of the proposed algorithm, an example is presented, setting of which is depicted in Figure 10.
For calculation of the initial lower bound, $L{B}_{i}{}^{0}$ is calculated by following:
So the initial lower bound of the problem is $\underset{\text{i}}{\mathrm{max}}L{B}_{i}{}^{0}$ = 232.67.
For initialization, set τ = 0.
When t = 0, all three L/U stations are available. For job allocation of the first L/U station, all types of parts are assignable, which means J ={1, 2, 3, 4, 5}.
For each assignable part ∈ J , τ′ and the projected lower bound $(\underset{k}{\text{max}}L{B}_{k}^{{\tau}^{\prime}}(j))$ is like below:
For $\begin{array}{r}j=1,\hspace{0.17em}{{\tau}^{\prime}}^{k}=\mathrm{max}\{\text{\tau},\hspace{0.17em}\text{t}+{l}_{1}\}=\text{max{}0,\hspace{0.17em}0+42\text{}}=42,\hspace{0.17em}\\ {u}_{k}^{l}(1,\hspace{0.17em}42),\hspace{0.17em}{r}_{k}^{l}(1,\hspace{0.17em}42),{r}_{k}^{m}(1,\hspace{0.17em}42)=0\text{}\forall k\\ {q}_{1}^{l}(1,\hspace{0.17em}42)=3;\hspace{0.17em}{q}_{i}^{l}(1,\hspace{0.17em}42),\hspace{0.17em}{q}_{i}^{m}(1,\hspace{0.17em}42)={q}_{i}\hspace{0.17em}for\hspace{0.17em}i=2,\hspace{0.17em}3,\hspace{0.17em}4,\hspace{0.17em}5;\\ {\mathrm{max}}_{k}L{B}_{k}^{42}(1)=L{B}_{2}^{42}(1)=263.5\end{array}$
For $j=2,\hspace{0.17em}\tau \prime =18\hspace{0.17em}{\mathrm{max}}_{k}L{B}_{k}^{18}(2)=240$
For $j=3,\hspace{0.17em}\hspace{0.17em}\tau \prime =33,\hspace{0.17em}\hspace{0.17em}{\mathrm{max}}_{k}L{B}_{k}^{33}(3)=269$
For $j=4,\hspace{0.17em}\hspace{0.17em}\tau \prime =29,\hspace{0.17em}\hspace{0.17em}{\mathrm{max}}_{k}L{B}_{k}^{29}(4)=248.33$
For $j=5,\hspace{0.17em}\hspace{0.17em}\tau \prime =30,\hspace{0.17em}\hspace{0.17em}{\mathrm{max}}_{k}L{B}_{k}^{30}(5)=248$
Therefore, part 2 $=\text{arg}\underset{j\text{}\in J}{\mathrm{min}}\{\underset{k}{\text{max}}\hspace{0.17em}L{B}_{k}^{{\tau}^{\prime}}(j)\}$ is allocated to the L/U station. And τ is updated max{τ,τ′} = max{0, 42} = 42.
For decisions afterward, dispatching information is depicted in Table 1.
The algorithm ends up with completion time 255 (min.), about 10% larger than the initial lower bound.
4. EXPERIMENT
To verify the performance of the proposed algorithm, an experiment was conducted.
Currently, hardware of a single RMC in development in the Korean NC machine maker supports up to 4 L/U stations and 9 NC machines. The number of supporting NC machines is larger than that of L/U stations, because usually machining time is larger than the loading (or setup) time. And this is reflected in experiment.
Five experimental factors were chosen to experiment various shop configurations and demands: the number of L/U stations, machines and pallets, and number of part types and production volume for each part type. Parameter information about processing times ( l_{i} and m_{i} ) were obtained from field data so that l_{i} ∼ UNIF(10, 50) min. and m_{i} ∼ UNIF(10,100) min., respectively. As for palletfixture assignment, the same number of total pallets was equally assigned for each part type and the remainder was assigned randomly.
As alternatives to be compared with the proposed algorithm, various dispatching rules and a heuristic search engine, iLOG CP, were taken into account. iLOG CP is a constraint programming based search engine that is known more appropriate for problems with disjunctive constraints such as scheduling problems, than exact algorithm based search engine, for example, iLOG CPLEX (IBM Corp, 2009). (It was also observed in pilot study that iLOG CP showed superior performance than iLOG CPLEX.) Description of alternative dispatching rule is depicted in Table 2. Additionally, the failure limit (the number of failures allowed before terminating a search. The ‘failure’, in here, means the search engine fails to find a feasible solution in a certain search direction.) of iLOG CP was set to ten thousands.
Performance was measured in the percentage gap from the initial lower bound $(\mathrm{max}L{B}_{i}^{0})$ given like below:
where C_{max} (r) is the makespan obtained from applying a dispatching rule or an algorithm r.
Finally for each experimental condition, average performance from 10 replications was recorded, together with the computational time spent for generating the schedules.
5. RESULT AND ANALYSIS
Table 3 and Table 4 show the result of the experiment for performance measure and computational time, respectively. Figure 11 to Figure 13 are graphical representation. A*(nonp.) indicates the case where the proposed algorithm is applied to determining both loading and machining sequence, allowing generation of nonpermutation schedules. A*(perm.) means the case where the algorithm is applied to sequencing only loading operation, forcing the same sequence of loading and the machining operations (i.e. permutation schedules).Figure 12
The result shows that the proposed nonpermutation algorithm (A*(nonp.)) consistently performs well over the alternative dispatching rules and iLOG CP for various shop configurations and demand settings. The performance of the least work remaining rule (LRK) and iLOG CP are relatively good, but the statistics — average, maximum and minimum performance value, and standard deviation — says that the proposed algorithm is superior to those alternatives as well.
On the other hand, the proposed permutation algorithm (A*(perm.)) appeared not to performs well, proving the nature of the scheduling problem that permutation schedules are not enough to find efficient solutions.
For computational time, as shown in Table 4 and Figure 13, the proposed algorithm appeared to generate the schedules as fast as the alternative dispatching rules, while the heuristic search engine iLOG CP spent about 10 to 100 times more to do the same job.
This result implies that the proposed algorithm performs consistent for various hardware configurations and demands and is able to generate a number of schedules quickly, therefore is an appropriate algorithm for hardware reconfiguration where various configurations need to be evaluated to find the best one, as explained in section 2. Moreover, the proposed algorithm may be applicable to manufacturing execution as well, where realtime decision making is required.
Experimental result also clarifies the efficacy of schedulinglevel evaluation in hardware reconfiguration. Actual performance of hardware configurations quiet differs from scheduling algorithms (1.69~20.92%) and even within a certain scheduling algorithm itself, according to cases (1.49~8.94%). It would be a very difficult job for production managers to predict performance of configuration alternatives without scheduling.
6. CONCLUSION AND FUTURE STUDY
This study has aimed to develop a scheduling algorithm for hardware reconfiguration of RMCs. As various configurations need to be evaluated and compared with respect to their schedules, the scheduling algorithm for hardware reconfiguration needs to perform consistent for various hardware configurations and to generate schedules in short computational time.
Through experiment it has been shown that the proposed algorithm generates schedules with performance near the lower bounds, higher than a constraint programming based search engine (iLOG CP) and benchmark dispatching rules, for various configurations and demands. It also appeared to generate schedules as fast as the dispatching rules.
The robustness of the proposed algorithm may be originated from the fact that the algorithm reflects shop configurations and demand information in its reasoning scheme (i.e. calculation of $L{B}_{i}^{\tau}$ ) and also looks ahead of the future status of the shop via workinprocess projection, unlike the conventional dispatching rules. The proposed algorithm is expected to be used in hardware reconfiguration of RMCs as a basic component.
As future study, an integrative framework for hardware reconfiguration covering whole stages of the flow chart in Figure 5 is required. Resolution may not be easy, for the number of possible alternatives is huge. Therefore a systematic framework to find the best hardware configuration needs to be developed. Moreover, it takes time for hardware reconfiguration and production may stop during reconfiguration. Hence, capacity loss from hardware reconfiguration should also be considered (For more result on this topic, refer Seo, 2014).