Abstract: The loading problem in a Cellular Manufacturing System (CMS) lies in the allocation of operations and associated cutting tools to machines for a given set of parts subject to capacity constraints. This research suggested a heuristic approach to the machine loading problem under the constraints of the workload and tool magazine capacity of each machine. This approach tried to reduce the maximum workload of the machines by partially grouping them. The processing time of the operation is different for each machine group, which is composed of the same identical machines; however, these machines can perform different sets of operations if tooled differently. The heuristic demonstrates the efficiency of allocating operations to each group and this problem is formulated as an integer linear problem. Performance of the suggested loading heuristics is tested by means of randomly generated tests. The result of this research, which is a well-balanced workload system, is obtained and partial grouping is a critical means of obtaining that goal. Partial grouping yields a more balanced workload because it entails the subdivision of demands into several batches.
INTRODUCTION
After product items and their quantities to be manufactured are determined by production planning, the next problem to be solved in production management is that of allocating the workloads to the existing production facilities for manufacturing these products. In general, the capacities (including human power) of the facilities are not infinite. Therefore, in order to actually perform production activities according to the production plan established, it is essential to adjust the workload for each of the facilities and workers in every time period so they do not exceed the given capacity. This decision is called machine loading.
After assigning an operation to multiple machines, a set of tools are loaded onto each machine that is required for that operation. This is one of the distinct characteristics of partial grouping. In other sorts of grouping, tools are loaded before operations are assigned, however, in partial grouping, necessary tools are loaded after operations allocated to each machine. It is this characteristic of partial grouping that makes each machine a virtual cell.
In most cases in the field of production planning and scheduling, the processing time required to complete a specified operation is set as a constant. In most of the existing research about loading problems with respect to partial grouping, the machine loading models were constructed under the assumption that the processing time is a constant. In practical situations, however, it is possible to vary the processing times by actively changing manufacturing conditions, especially machining speeds. In these cases, some modifications must be made to production planning and scheduling models. To be useful, those models require a new type of heuristic that allows for variation in processing times. This research is concerned with machine loading models that have variable processing times.
The most significant contributions of the research described in this research are (1) the development of a good heuristic in a loading problem with variable processing time for each cluster; (2) assigning the operations into clusters. (3) the implementation of different heuristics, according to phase. Operations are assigned to clusters while each cluster has a different processing time. (4) the attempt to address the loading problem with respect to each machine’s capacity and workload limit, which impact loading problem performance.
There is extensive literature on assembly line and workload balancing in job shops and Cellular Manufacturing System (CMS). Balancing is appropriate for flexible assembly systems as well as automated transfer lines. Stecke and Solberg (1981) employed loading and control policies for a flexible manufacturing system and defined loading and control methods that significantly improve system production rates. Stecke (1986) considered various operation assignment objectives appropriate in FMS and presented a hierarchical framework for considering these objectives. Berrada and Stecke (1986) applied a branch and bound algorithm to solve the workload balancing problem for all machines when each machine’s processing time is different. A new branch and bound algorithm was developed, based on the work of Berrada and Stecke (1986). This new algorithm was developed to maximize the expected production rate (throughput) of the system and to ensure that actual workload allocation is commensurate with the continuous workload allocation that maximizes throughput. There are various algorithms for the identical processor minimum-makespan scheduling problem and for some of them the worst case performance ratios are known. The LPT algorithm has a worst case performance ratio of 4/3-1/3 m, where, m is the number of processors (machines) and the Multifit algorithm has a worst case performance ratio of 1.2+(1/2)k, where, k is the number of iterations in the algorithm (Coffman et al., 1978; Friesen, 1984; Graham, 1969). Lee and Kim (2000) implemented several loading algorithms for flexible-manufacturing systems with partially grouped machines. They formulated the loading problem by means of integer programming and primarily utilized LPT and Multifit algorithms. They described two means of addressing this problem. One approach was direct, whereas, the other decomposed the problem into the operation assignment problem and the workload allocation problem. Both approaches implemented LPT and Multifit algorithms, yet a comparison of the results demonstrated that decomposition methods are better that direct ones. Additionally, simulation experiments demonstrated that partial grouping loading plans yielded significantly better performance than total grouping loading plans. Chen and Askin (1990) performed heuristics, based on the separate evaluation of five objectives: workload balance, volume of inter-machine part movement, routing flexibility, tool investment and maximum machine utilization. Choi and Lee (1998) developed heuristic procedures with the two-part objective of minimizing workload imbalances and maximizing system throughput. Their solution hinged on the rejection factor and virtual total processing time. Shanthikumar and Stecke (1986) showed that maintaining balanced workloads on each machine over time stochastically minimizes work-in-process inventory requirements for FMS that contain only one machine in a group. Stecke and Morin (1985) have shown that if each operation is assigned to only one machine, balancing the workload of each machine maximizes expected production by using symmetric mathematical programming. Nagarjuna et al. (2006) proposed a heuristic to minimize the system unbalance based on multi-stage programming approach. Ponnambalam and Kiat (2008) also tried to minimize system unbalance and additionally maximizing system throughput by using of a particle swarm optimization algorithm.
The aim of this research was to investigate the formulation of the loading problem as an integer programming problem, to develop a solution algorithm based on the formulation of the problem and to test solution methodologies. Eventually, these procedures will minimize the maximum workload for each machine.
MODEL DEVELOPMENT
The purpose of this problem is to assign each operation to machines. In order to assign operations to machines, those operations must be assigned to cluster first and then they can be assigned to machines in each cluster. The machines used for these CMS have automatic tool changers and a tool magazine of a limited capacity and can work limited time for each day. To execute an operation, one or more tools are required and each tool requires one or more slots in the tool magazine. Another significant feature of this system is tool sharing or tool commonality. In other words, several operations may share the same tools in the system. Operations require several tools: yet if different operations are allocated to the same cluster or different machines use the same tool, then duplicated tools are not assigned to the same cluster or machine.
If operations require different processing times, they are considered different operations even though they are the same type. For instance, drilling operations for different part types are treated as different operations if their processing times are different-even though they require the same set of tools. The loading problem allocates operations and associated tools to machines in order to minimize the maximum workload of the machines subject to tool magazine capacity and workload capacity constraints. An integer linear problem provides a clear description of this loading problem. The following notations are used in its formulation.
The notation used in problem formulation is presented:
| I | = | Index for operation, iεI |
| j | = | Index for machine, jεJ |
| t | = | Index for tools, tεT |
| k | = | Index for machine type, kεK |
| c | = | Index for machine cluster, cεC |
| pi | = | Processing time of operation i |
| pki | = | Processing time of operation i for machine type k |
| C | = | Capacity of a tool magazine of a machine cluster j in cluster c |
| Wcj | = | The workload for a machine j in the cluster |
| Wc | = | The maximum workload allowed for a cluster c |
| Di | = | Demands of operation i |
| st | = | Number of tool slots needed for too t |
| bic | = | Batches for operation i that is assigned to machine clustec |
| |G| | = | Number of cluster |
| ait | = | |
| xic | = | |
| yic | = |
Formulation
Minimize Z, subject to:
| (1) |
| (2) |
| (3) |
| (4) |
| (5) |
| (6) |
| (7) |
| (8) |
| (9) |
In the formulation, constraint set (1) explains that operations can be assigned to any machine cluster and workload for each cluster is restricted. Constraint set (2) defines the sum of all workloads of the machines in each cluster. The number of clusters allocated to each operation should not be greater than the total number of clusters is denoted in constraint set (3). Constraint set (4) shows the relationship between bic and xic, which is the batches of operation i can be allocated to cluster c (bic) only if xic=1. Constraint set (5) shows that the sum of all batches to be assigned to each cluster in each operation is the demand of each operation. Constraint set (6) illustrates that the required tools for the operation to be loaded onto each cluster where the operation is allocated. Constraint sets (7) bound the number of parts that can be processed on a cluster and a machine within a cluster.
PROPOSED RESEARCH PROCEDURE
Four heuristics and a Multifit algorithm for each heuristic will be implemented in this research. The first Heuristic selects the maximum batch workload for each cluster and then selects the minimum batch workload among them. The second Heuristic selects the minimum batch workload value for each cluster and then selects the minimum batch workload value among them instead of selecting the maximum batch workload value of the minimum from the cluster types. The third Heuristic selects the maximum batch workload value for each cluster and then selects the maximum batch workload value from among them. The fourth Heuristic selects the minimum batch workload value in each cluster and then chooses the maximum batch value among them. By means of these trials, we can determine which of the four Heuristics provides the best performance. The modified Multifit algorithm will be applied with each Heuristic. Wc and Cc are control parameters for the heuristic. When assigning operations, we use Wc and Cc to limit the operation aggregation process. As Wc increases, fewer but longer operations will be fed to the solution procedure. Material handling should decline but workload balancing may become more difficult in the cluster.
We will use the term Δλic as a dynamic variable to indicate the number of machine tool slots that must be added to cluster type cto perform operation i. This term is dynamic in the sense that it depends on which tools have already been assigned to c. For example, if two operations use the same tool and the first operation is assigned to clusters, the second operation must then use additional tool slots.
And the term Δηic will be used as a dynamic variable for denoting the workload limit for each cluster. There is a workload limit for each machine and the total workload limit for the machines within each cluster is the workload limit for that cluster. This workload limit value is decreased as it is when assigning operations to clusters. If the workload limit for each cluster has the negative value, then the system is infeasible.
The tool magazine capacity for each cluster defines the system in the same way. If the system is infeasible, then the system stopped and other variables are generated for it. If these problems happen repeatedly, then tool magazine capacities and workload limits for each machine must be considered. Flexible workload limits maximize the probability that all of the operations can be assigned to clusters; however, they also lower utilization. The main factor that we need to consider is the workload, because the objective is minimize the maximum workload so that we can minimize the lead time with these results.
General Procedure for Heuristic
| Step 1: | Initialize maximum workload and maximum tool capacity |
| Step 2: | Make batches for each operation by dividing demands of an operation by the number of clusters (Batches must be integers, so if demand=10 and the number of machines is 3, then the batches are 3, 3, 4) |
| Step 3: | Initialize batch workload by multiplying batch and processing time for each operation |
| Step 4: | In each cluster, select the minimum batch workload and then select the maximum batch workload from those previously selected |
| Step 5: | For the operations that have been selected, select operations that have the same batch number for each cluster |
| Step 6: | For all selected operations for each cluster, select if maximum workload limit selected batch workload (Δηic)> 0 and maximum tool capacity-the number of tool (Δλic) > 0 |
| Step 7: | Select maximum value of maximum workload limit – selected batch workload (Δηic) |
| Step 8: | Assign operation to the cluster that has the largest remaining workload capacity if tools were assigned previously, then do not allocate again. Update maximum workload limit and maximum tool capacity |
| Step 9: | Repeat until all operations are allocated |
| Table 1: | Selection rule for operation assignments |
| Table 2: | Generating loading problem data sets |
| Table 3: | Configurations for running loading problems |
Table 1 presents configurations for each Heuristics. Unfortunately, it is extremely difficult to obtain actual data for a wide variety of systems because most are proprietary. In order to overcome this limitation, test problems have been generated randomly to ensure that the resulting data represent real systems relatively well. Test case data was randomly generated using the parameters and test levels provided in Table 2 and 3.
Four Heuristics are shown in the first column. The second column shows how to select between clusters. The third column describes the means for selecting operations in column two. The last column describes the means for allocating operations to each cluster. The Multifit algorithm will be implemented for each Heuristic case.
RESULTS
This research has not been done in any other previous research, so we decided to show the performance of result by comparing the outcome with performance ratio, which is lower bound. Solutions from the algorithms were compared with each other using the performance ratio as an index; this is the ratio to a lower bound, i.e.,
After implementing all of the Heuristics, a relative performance ratio, which is defined by as [(Hh-HB)/Hh]x100, will be shown in order to evaluate the results. HB is the best performance ratio and Hh is the performance ratio from the Heuristic.
| Table 4: | Relative performance in cluster 3 |
| Table 5: | Relative performance in cluster 4 |
Given these results of loading problem computational experiments, one can infer that relative performance is good and can be applied in real factory problem. Between relative performance ratio for 8 heuristics in each cluster in the Table 4-6, Heuristic III performed well.
The result of Heuristic III shows very low performance ratio, which is close to 0. It means that the outcome of this Heuristic III is very close to lower bound. We expect this result will reduce lead times and operating costs. Furthermore, such outputs may be obtained in a reasonable running time.
In analyzing this loading problem, this research has made several contributions. The first was the identification and formal modeling of the loading problem. The integer linear programming models presented were extensions of known models for the loading problem. A second contribution was the ability to deal with different processing times in different clusters for the same operation. This reflects the scenario in which an operation can be processed on machines of different types.
| Table 6: | Relative performance in cluster 5 |
ACKNOWLEDGMENT
This study was supported by Research Fund, Kumoh National Institute of Technology.