Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.17 No.1 pp.14-29

Development of a Scheduling Algorithm for Reconfigurable Manufacturing Cells

Jinwu Seo, Hanil Jeong*, Jinwoo Park
MES-team, Samsung SDS, Seoul, Republic of Korea
Department of IT Business Engineering, Daejeon University, Daejeon, Republic of Korea
Department of Industrial Engineering, Seoul National University, Seoul, Republic of Korea
Corresponding Author,
October 5, 2016 March 3, 2017 October 11, 2017


RMCs (Reconfigurable Manufacturing Cells) are production systems which can rapidly change hardware configurations to respond to market variance. Given market demand, manufacturing performance may differ from hardware configurations. To evaluate and compare possible hardware configurations, scheduling may be required. Since schedules specify detailed resource allocation of hardware configurations in concern, managers may make decisions with certainty based on schedules. Previous studies, however, neither provided accurate evaluation of manufacturing performance, nor developed scheduling algorithms in consideration of hardware reconfiguration. The scheduling algorithms for hardware reconfiguration should perform consistent for various hardware configurations and generate schedules as fast as possible. This study aims to develop a scheduling algorithm for RMCs as a basic component of hardware reconfiguration. After a mathematical model which represents the scheduling problem is built, a lower boundbased look-ahead scheduling algorithm is proposed from the thorough analysis of the problem. Experimental result shows 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.



    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 re-arrangement 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.

    Scheduling-level evaluation of hardware configurations provides reliable information for decision-making. 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 scheduling-level evaluation, therefore, managers may make decisions with certainty.

    Studies that provide scheduling-level 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 petri-net to generate the reconfiguration plan in combination with the corresponding schedule. The petri-net 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 long-term (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 ever-changing 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 short-term demand forecast is relatively accurate and difference from actual demand is relatively small, scheduling-level evaluation of RMCs would be meaningful for reliable decision-making.

    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.


    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 multi-cell 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 part-grouping 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 pallet-fixture assignment specifies which fixtures are to be installed on pallets. Figure 7 indicates the example of the pallet-fixture assignment. The pallet-fixture assignment is giv-en 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 re-source and there exist enough capacity of tool maga-zine. Therefore the part-loading problem or part-mix allocation problem (Lee and Kim, 1996) is not consid-ered here. Besides, deterministic operation time is as-sumed and material handling time and the size of buff-ers 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 esti-mate 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 on-off 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 work-pieces, fixtures and cutting tools. Seo and Park (2011) dis-cussed about how to improve practicality of FMS schedulers and presented a database structure and Na et al. (2011) investigated the FMC scheduling and re-scheduling problems during transient disturbance period, both considering pallet-fixture assignment. However above studies were conceptual not suggesting any algo-rithm or methodology for resolution.

    Shalev-Oren and Schweitzer (1985) presented an analytic model based on the mean value analysis to measure performance of FMS according to priority rules considering the pallet-fixture 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 network-based models have an advantage in fast obtaining of steady-state performance, but are lim-ited in that only simple queuing disciplines are applica-ble and there usually exists an error between estimated performance and actual (or simulated) result. In Shalev-Oren et al. (1985) the estimated result was compared with the actual and appeared to have difference of around 4-13% 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, opera-tion/machine selection, and part sequencing and exam-ined performance of various combinations of priority rules. Han et al. (2012) dealt the case where the pallet-fixture assignment is decidable and tried to improve manufacturing performance in an integrative manner. Sethi et al. (1999) verified performance of Gilmore-Gomory’s algorithm proposed by Gilmore and Gomory (1964) for scheduling two stage pallet-constrained 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 pre-sented for further problem analysis and algorithm de-velopment.

    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

    • li : Part i’s loading (or setup) time

    • mi : Part i’s machining time

    • qi : Production quantity (or demand) for part i

    • L : The number of L/U stations

    • M : The number of NC machines

    • pi : 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 ( li and mi ) 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 i t l , S i t m : The number of parts of type i which start its loading or machining operations at time t

    • Dependent variables

    • C i t l ,   C i t m : The number of parts of type i which complete its loading or machining operations at time t

    • R t l ,   R t m : The number of L/U stations or NC machines which process parts at time t

    • Ait : The number of pallets for type i which are occupied by parts for processing at time t

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

    • Cmax : The maximum completion time or makespan

    The expected range of the makespan ( Cmax ) 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 two-stage hybrid flowshop scheduling problem, which is NP-complete (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.


    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

    L B 1 0 = l i × q i min ( L , q i ) + min i m i

    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

    L B 2 0 = min i l i + m i × q i min ( M , q i )

    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:

    l b PA ( k ) 0 =  ( l k + m k ) × q k p k

    Finally the pallet-based lower bound is like below:

    3.1.3 The Lower Bound in Pallet Bottleneck Case

    L B 3 0 = max k l b PA ( k ) 0 = max k ( l k + m k ) × q k p k

    Definitely, z * max i   L B i 0 . This information of lower bounds may be used as an estimator for z * .

    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 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, a t 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 (li), at t = b = c + li , the amount of WIP waiting for machining operations increases as much as the machining time (mi). Conversely, if a machining operation of part type i is allocated to a NC machine, then after the machining time (mi), 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 pallet-constraint 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 ( max i   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 jJ , calculate the projected lower bound ( max k   L B k τ ( j ) ) for the future time τ = max { τ , t + l j k ( or m j ) }

    • (2.3) Assign an operation p = arg min j   J { max k L B k τ ( 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 τ ( j ) is the projected lower bound of kth type for time τ′, if part jJ is assigned to available equipment at the decision point, based on decisions made so far. Detail information is given below:

    L B 1 τ ( j ) = l i × q i l ( j , τ ) + r k l ( j , τ ) min ( L ,   q i l ( j , τ ) + u k l ( j , τ ) ) + min i : q i m ( j , τ ) > 0 m i  
    L B 2 τ ( j ) = { min k r k l ( j , τ )   +   m i × q i m ( j , τ ) + r k m ( j , τ ) min ( M ,   q i m ( j , τ ) + u k m ( j , τ ) ) ,   i f   u k m ( j , τ ) > 0   min i : q i l ( j , τ ) > 0 l i   +   m i × q i m ( j , τ ) + r k m ( j , τ ) min ( M ,   q i m ( j , τ ) + u k m ( j , τ ) ) ,   o t h e r w i s e
    L B 3 τ ( j ) = max k ( l k × q k l ( j , τ ) + v : F ( v ) = k   r v l ( j , τ ) + m i × q i m ( j , τ ) + v : F ( v ) = k   r v m ( j , τ ) ) × q k p k


    • u k l ( j , τ ) , u k m ( j , τ ) : 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: non-exists).

    • r k l ( j , τ ) ,   r k m ( j , τ ) : 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 , τ ) , q i m ( j , τ ) : 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 τ ( j ) , L B k 0 is extended so that it would reflect the future system status which is derived by work-in-process 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:

    L B 1 0 = l i × q i min ( L , q i ) + min i m i = 432 min ( 3 , 14 ) + 15 = 159
    L B 2 0 = min i l i + m i × q i min ( M , q i ) = 18 + 644 min ( 3 , 14 ) = 232.67
    l b PA(1) 0 = ( l 1 + m 1 ) × q 1 p 1 = ( 42 + 60 ) × 4 2 = 204
    l b PA(2) 0 = ( 18 + 60 ) × 3 2 = 156
    l b PA(3) 0 = ( 33 + 20 ) × 1 2 = 53
    l b PA(4) 0 = ( 29 + 15 ) × 3 2 = 132
    l b PA(5) 0 = ( 30 + 53 ) × 3 2 = 166
    L B 3 0 = max k l b PA ( k )   0 = 204

    So the initial lower bound of the problem is max i 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 ( max k   L B k τ ( j ) ) is like below:

    For j = 1 , τ k = max { τ , t + l 1 } = max{ 0 , 0 + 42 } = 42 , u k l ( 1 , 42 ) , r k l ( 1 , 42 ) , r k m ( 1 , 42 ) = 0   k q 1 l ( 1 , 42 ) = 3 ; q i l ( 1 , 42 ) , q i m ( 1 , 42 ) = q i f o r i = 2 , 3 , 4 , 5 ; max k L B k 42 ( 1 ) = L B 2 42 ( 1 ) = 263.5

    For j = 2 , τ = 18 max k L B k 18 ( 2 ) = 240

    For j = 3 , τ = 33 , max k L B k 33 ( 3 ) = 269

    For j = 4 , τ = 29 , max k L B k 29 ( 4 ) = 248.33

    For j = 5 , τ = 30 , max k L B k 30 ( 5 ) = 248

    Therefore, part 2 = arg min j   J { max k L B k τ ( 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.


    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 ( li and mi ) were obtained from field data so that li ∼ UNIF(10, 50) min. and mi ∼ UNIF(10,100) min., respectively. As for pallet-fixture 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 ( max   L B i 0 ) given like below:

    %Gap = C m a x ( r ) max i   L B i 0 max i L B i 0 × 100

    where Cmax (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.


    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*(non-p.) 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 non-permutation algorithm (A*(non-p.)) 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 real-time decision making is required.

    Experimental result also clarifies the efficacy of scheduling-level 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.


    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 τ ) and also looks ahead of the future status of the shop via work-in-process 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).


    This research was supported by the Daejeon University Research Grants (2016).



    Typical RMC.


    The concept of reconfiguring.


    Manufacturing performance according to configurations.


    Manufacturing performance of a configuration and RMC schedules.


    The Flow chart for hardware reconfiguration.


    Production environment: A typical layout of a factory.


    Example of the pallet-fixture assignment.


    Impact of resource idleness.


    Work-in-process projection.


    Example setting.


    Experimental result for performance measure (%Gap).


    Experimental result for performance measure (%Gap, selected and zoomed).


    Experimental result for computational time (excluding iLOG CP).


    Dispatching information for the example of the proposed algorithm

    Dispatching rules used in experiment as alternatives

    Experimental result for performance measure (%Gap)

    Experimental result for computational time (millisecond)


    1. K.R. Baker (1974) Introduction to Sequencing and Scheduling., John Wiley and Sons,
    2. A. M. Deif (2006) A control approach to explore the dynamics of capacity scalability in reconfigurable manufacturing systems., J. Manuf. Syst., Vol.25 (1) ; pp.12-24
    3. D.R. Denzler , W.J. Boe , E. Duplaga (1987) An experimental investigation of FMS scheduling rules under uncertainty., J. Oper. Manage., Vol.7 (1-2) ; pp.139-151
    4. H.A. ElMaraghy (2006) Flexible and reconfigurable manufacturing systems paradigms., Int. J. Flex. Manuf. Syst., Vol.17 (4) ; pp.261-276
    5. P. Gilmore , R. Gomory (1964) Sequencing a one state-variable machine: A solvable case of the traveling salesman problem., Oper. Res., Vol.12 (5) ; pp.655-679
    6. J.N.D. Gupta (1988) Two-stage, hybrid flowshop scheduling problem., J. Oper. Res. Soc., Vol.39 (4) ; pp.359-364
    7. S. Han , J. Seo , J. Park , J. Lee , K. Kang , S. Lee , J. Moon (2012) Pallet-fixture allocation in reconfigurable manufacturing cells: An integrative approach., Journal of the Korean Society for Precision Engineering, Vol.29 (4) ; pp.357-366
    8. I.B.M. Corp (2009)
    9. D. Lee , Y. Kim (1996) Part-mix allocation in a hybrid manufacturing system with a flexible manufacturing cell and a conventional job shop., Int. J. Prod. Res., Vol.34 (5) ; pp.1347-1360
    10. S. Lee , J. Lee , D. Kim , H. Kim , S. Nam (2010) Development of integrated operation technology for autonomous reconfigurable production system, Proceedings of the 2010 Fall Conference of the Korean Society of Machine Tool Engineers, ; pp.167-169
    11. J. Liu , B.L. MacCarthy (1996) The classification of FMS scheduling problems., Int. J. Prod. Res., Vol.34 (3) ; pp.647-656
    12. B.L. MacCarthy , J. Liu (1993) A new classification scheme for flexible manufacturing systems., Int. J. Prod. Res., Vol.31 (2) ; pp.229-309
    13. M. Mashaei , B. Lennartson (2013) Energy reduction in a pallet-constrained flow shop through on-off control of idle machines., IEEE Trans. Autom. Sci. Eng., Vol.10 (1) ; pp.45-56
    14. M.G. Mehrabi , A.G. Ulsoy , Y. Koren (2000) Reconfigurable manufacturing systems: Key to future manufacturing., J. Intell. Manuf., Vol.11 (4) ; pp.403-419
    15. H. Na , J. Seo , J. Park (2011) A study on scheduling and rescheduling problem of the FMC during transient disturbance period with pallet constraints, Proceedings of the 21st International Conference on Production Research,
    16. X. Nan , L. Aiping , Y. Jianxin (2007) Product scheduling and manufacturing line reconfiguration using petri nets and heuristic search, Proceedings of the 2007 IEEE International Conference on Robotics and Biomimetics, ; pp.1721-1726
    17. M. Pinedo (1995) Scheduling - theory, algorithms, and systems., Prentice Hall,
    18. S. Rahimifard , S.T. Newman (1999) The application of information systems for the design and operation of flexible machining cells., J. Intell. Manuf., Vol.10 (1) ; pp.21-27
    19. J. Seo , J. Park (2011) Developing a practical machine scheduler for worker-involved systems, Proceedings of the Asia Simulation Conference, ; pp.316-325
    20. J. Seo , J. Park (2013) The effect of enhanced flexibility in the reconfigurable manufacturing cell, Proceedings of the 22nd International Conference on Production Research,
    21. J. Seo (2014)
    22. S.P. Sethi , C. Sriskandarajah , S.V.D. Velde , M.Y. Wang , H. Hoogeveen (1999) Minimizing makespan in a pallet-constrained flowshop., J. Sched., Vol.2 (3) ; pp.115-133
    23. S. Shalev-Oren , A. Seidmann , P.J. Schweitzer (1985) Analysis of flexible manufacturing systems with priority scheduling: PMVA., Ann. Oper. Res., Vol.3 (3) ; pp.115-139
    24. P. Solot , J.M. Bastos (1988) MULTIQ: A queueing model for FMSs with several pallet types., J. Oper. Res. Soc., Vol.39 (9) ; pp.811-821
    25. P. Solot (1990) A heuristic method to determine the number of pallets in a flexible manufacturing system with several pallet types., Int. J. Flex. Manuf. Syst., Vol.2 (3) ; pp.191-216
    26. R. Soto , B. Crawford , E. Monfroy , V. Bustos (2012) Using autonomous search for generating good enumeration strategy blends in constraint programming., Lect. Notes Comput. Sci., Vol.7335 ; pp.607-617
    27. P. Spicer , H.J. Carlo (2007) Integrating reconfiguration cost into the design of multi-period scalable reconfigurable manufacturing systems., J. Manuf. Sci. Eng., Vol.129 (1) ; pp.202-210
    28. H. Ye , M. Liang (2006) Simultaneous modular product scheduling and manufacturing cell reconfiguration using a genetic algorithm, Transactions of the ASME, ; pp.984-995
    29. A.M.A. Youssef , H.A. ElMaraghy (2006) Modelling and optimization of multiple-aspect RMS configurations., Int. J. Prod. Res., Vol.44 (22) ; pp.4929-4958
    30. J. Yu , H. Doh , H. Kim , J. Kim , D. Lee , S. Nam (2012) Iterative algorithms for part grouping and loading in cellular reconfigurable manufacturing system., J. Oper. Res. Soc., Vol.63 (12) ; pp.1635-1644
    31. B. Zheng , W. Xue , X. Xie (2010) Configuration optimization of manufacturing system based resource reconfiguration, Proceedings of 2nd International Conference on Mechanical and Electronics Engineering, ; pp.193-195
    Do not open for a day Close