Integrated assembly line balancing with resource restrictions

This paper documents a study carried out on the problem of designing an integrated assembly line when many workers with a variety of skills are employed. This study addresses the problem of selecting multi-functional workers with different salaries to match their skills and of assigning tasks to work stations when there are precedence restrictions among the tasks. The objective of this study is to minimise the total annual work station costs and the annual salary of the assigned workers within a predetermined cycle time. A mixed integer linear program is developed with a genetic algorithm in order to address the problem of resource restrictions related to integrated assembly line balancing. Numerical examples demonstrate the efficiency of the developed genetic algorithm.     

Group scheduling problem: Key to flexible manufacturing systems

We present an efficient heuristic algorithm for determining the sequence which minimizes the makespan of a group scheduling problem at the first level. The problem, therefore, focuses on scheduling of parts (jobs) in a part family. In the generation of partial schedules at each iteration, a job with a high mean total processing time is given a higher priority than others. An example problem, chosen from a real world application, is used to implement, the algorithmic steps. For this example, it has also been shown that the makespan determine by the proposed heuristic is smaller than that determined previously by two documented algorithms.     

Sequence-dependent group scheduling problem on unrelated-parallel machines

In this research we address a sequence-dependent group scheduling problem on a set of unrelated-parallel machines where the run time of each job differs on different machines. To benefit both producer and customers we attempt to minimize a linear combination of total weighted completion time and total weighted tardiness. Since the problem is shown to be NP-hard, meta-heuristic algorithms based on tabu search are developed to find the optimal/near optimal solution. For some small size yet complex problems, the results from these algorithms are compared to the optimal solutions found by CPLEX. The result obtained in all of these problems is that the tabu search algorithms could find solutions at least as good as CPLEX but in drastically shorter computational time, thus signifying the high degree of efficiency and efficacy attained by the former.     

Effective two-phase p-median approach for the balanced cell formation in the design of cellular manufacturing system

In this paper, we present an effective two-phase p-median approach for the balanced cell formation (CF) in the design of cellular manufacturing system. In phase 1, the p-median mathematical model of machine CF, which adopts a linear integer programming formulation, is developed. Our formulation uses a new similarity coefficient based on the generalised nonbinary part-machine incidence matrix (PMIM) which incorporates realistic manufacturing aspects such as setup time, processing time, operation sequences and lot size of parts and duplicate machine types. In phase 2, a systematic part assignment procedure based on the new classification scheme of part types is established in pursuit of balancing the workload among machine cells. New efficiency measures for evaluating the quality of the binary and nonbinary PMIM-based block diagonal solutions are proposed to judge the degree of cell load imbalance. Computational experiments with moderately intermediate-sized data-sets selected from the literature show effectiveness of our two-phase p-median approach for the balanced CF.     

Makespan minimization of a flowshop sequence-dependent group scheduling problem

The flowshop sequence dependent group scheduling problem with minimization of makespan as the objective (F _m |fmls, S _plk, prmu|C _max ) is considered in this paper. It is assumed that several groups with different number of jobs are assigned to a flow shop cell that has m machines. The goal is to find the best sequence of processing the jobs in each group and the groups themselves with minimization of makespan as the objective. A mathematical model for the research problem is developed in this paper. As the research problem is shown to be NP-hard, a hybrid ant colony optimization (HACO) algorithm is developed to solve the problem. A lower bounding technique based on relaxing a few constraints of the mathematical model developed for the original problem is proposed to evaluate the quality of the HACO algorithm. Three different problem structures, with two, three, and six machines, are used in the generation of the test problems to test the performance of the algorithm and the lower bounding technique developed. The results obtained from the HACO algorithm and those that have appeared in the published literature are also compared. The comparative results show that the HACO algorithm has a superior performance compared to the best available algorithm based on memetic algorithm with an average percentage deviation of around 1.0% from the lower bound.     

Simultaneous machine-part grouping approach in manufacturing cells

We present a comprehensive model including all of the operational constraints for solving a cell formation problem in cellular manufacturing systems. It is formulated as a generalized quadratic binary programming model with the objective of minimizing total moves evaluated as a weighted sum of inter- and intracell moves. Two most significant operational constraints included in the model are the sequence of operations associated with each part and the capability of assigning machines of the same type to different cells if two or more machines are considered due to workload requirements. The original model is Transformed into a linear binary programming model, and an example problem is solved using a commercial programming package. The final assignment of parts and machines to cells result in a lower total move than that evaluated from a previous study for the same problem.     

A machine-part based grouping algorithm in cellular manufacturing

A model and a suitable solution algorithm have been presented for determining optimal/near optimal part-machine clusters in cellular manufacturing. The total moves generated by parts have been evaluated as a weighted sum of both inter- and intracell moves. In particular, the intercell move has been evaluated as the number of bottle-neck machines a part is required to visit to complete its processing requirements. The in-cell machine utilization has been included as an important measure, and a targeted minimum utilization of 50% has been used for the purpose of application. A hypothetical problem has been developed and solved to test the effectiveness of the solution algorithm and the validity of the model. The results demonstrate that the model can be used as a suitable decision making tool by small and medium sized parts manufacturing companies in their production planning.     

Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups

This paper focuses on minimizing the total completion time in two-machine group scheduling problems with sequence-dependent setups that are typically found in discrete parts manufacturing. As the problem is characterized as strongly NP-hard, three search algorithms based on tabu search are developed for solving industry-size scheduling problems. Four different lower bounding mechanisms are developed to identify a lower bound for all problems attempted, and the largest of the four is aptly used in the evaluation of the percentage deviation of the search algorithms to assess their efficacy. The problem sizes are classified as small, medium and large, and to accommodate the variability that might exist in the sequence-dependent setup times on both machines, three different scenarios are considered. Such finer levels of classification have resulted in the generation of nine different categories of problem instances, thus facilitating the performance of a very detailed statistical experimental design to assess the efficacy and efficiency of the three search algorithms. The search algorithm based on long-term memory with maximal frequencies either recorded a statistically better makespan or one that is indifferent when compared with the other two with all three scenarios and problem sizes. Hence, it is recommended for solving the research problem. Under the three scenarios, the average percentage deviation for all sizes of problem instances solved has been remarkably low. In particular, a mathematical programming based lower bounding mechanism, which focuses on converting (reducing) the original sequence-dependent group scheduling problem with several jobs in each group to a sequence-dependent job scheduling problem, has served well in identifying a high quality lower bound for the original problem, making it possible to evaluate a lower average percentage deviation for the search algorithm. Also, a 16–17-fold reduction in average computation time for solving a large problem instance with the recommended search algorithm compared with identifying just the lower bound of (not solving) the same instance by the mathematical programming based mechanism speaks strongly in favor of the search algorithm for solving industry-size group scheduling problems.     

Periodic product distribution from multi-depots under limited supplies

Physical distribution is one of the key functions in logistics systems, involving the flow of products from manufacturing plants or distribution centers through the transportation network to consumers. It is a very costly function, especially for the distribution industries. While maintaining the desired customer service levels, an effort is made in this paper to improve distribution strategies and reduce the distribution cost for the multi-product, multi-depot periodic distribution problem. In industry practice, depots typically operate independently and solely within their own territories. However, it may be beneficial to allow those depots to operate interdependently, particularly when the product supplies are limited at some depots. In such cases, the distributors may satisfy customers' requests by delivering products from other depots that hold more supplies. In particular, the impact of interdependent operations among depots, which has not previously been addressed in the context of industrial applications, is investigated in this research. A mixed-integer linear programming model is formulated to represent the multi-product, multi-depot periodic distribution problem. Three tabu search heuristics with different long-term memory applications are developed to solve the problem. The performance of the heuristics is evaluated by comparing the solutions obtained with the optimal solutions or lower bounds from the regular branch-and-bound method as well as a fast technique to find a lower bound that is developed in this research. The heuristics provide optimal/good quality solutions in a much shorter time. A randomized complete block design is applied to test the performance of the heuristics on various problem structures. The experimental results show that the tabu search heuristic that incorporates the use of a long-term memory in the diversification process outperforms the other heuristics. The heuristic is further applied to investigate the impact of interdependent operations among depots. The results reveal that interdependent operations among depots provide significant savings in costs over independent operations among depots, especially for large-size problems.     

Group-scheduling problems in electronics manufacturing

This paper addresses the flowshop group-scheduling problems typically encountered in the assembly of printed circuit boards in electronics manufacturing. A mathematical programming model is formulated to capture the characteristics inherent to group-scheduling problems experienced in electronics manufacturing as well as those common to a wide range of group-scheduling problems encountered in other production environments. Several heuristics, each incorporating different components that underlie the tabu search concept, are developed to solve this strongly NP-hard problem effectively in a timely manner. In order to investigate the quality of the heuristic solutions with respect to tight lower bounds, an effective and efficient decomposition approach is developed. The problem is decomposed into a master problem and single-machine subproblems, and a column generation algorithm is developed to solve the linear programming relaxation of the master problem. Branching schemes, compatible with the column generation subproblems, are employed to partition the solution space when the solution to the linear programming relaxation is not integral. Furthermore, tabu search based fast heuristics are implemented to solve the subproblems, and an effective stabilization method is developed to accelerate the column generation approach. An experimental design with both fixed and random factors accompanied by rigorous statistical analyses of computational tests conducted on randomly generated test problems as well as on a large size real industry problem confirm the high performance of the proposed approach in identifying quality lower bounds and strongly suggest its flexibility and applicability to a wide range of real problems.