Search

The Generalised MAchine Layout Problem (GMALP) is a generalisation of the integrated machine and layout problem, which is an extension of the machine layout problem. More specifically, the GMALP is the designing of a facility layout by defining the product mix, selecting the number of machines to be used, assigning these machines to the plant floor, and assigning products to machines such that total profit is maximised. Moreover, the GMALP integrates the quadratic assignment problem with a multicommodity flow problem. Therefore, the GMALP is a computationally intractable problem. Consequently, a mixed-integer nonlinear programming model was developed and used to solve small problem instances. Also, two simple construction algorithms and a tabu search (TS) heuristic were developed for solving large GMALP instances in acceptable computation times. In addition, a test dataset was used to evaluate the performances of the TS heuristic using the different construction algorithms. The results show that the TS he...

This paper presents a single instruction multiple data tabu search (SIMD-TS) algorithm for the quadratic assignment problem (QAP) with graphics hardware acceleration. The QAP is a classical combinatorial optimisation problem that is difficult to solve optimally for even small problems with over 30 items. By using graphic hardware acceleration, the developed SIMD-TS algorithm executes 20 to 45 times faster than traditional CPU code. The computational improvement is made possible by the utilisation of the parallel computing capability of a graphics processing unit (GPU). The speed and effectiveness of this algorithm are demonstrated on QAP library problems. The main contribution of this paper is a fast and effective SIMD-TS algorithm capable of producing results for large QAPs on a desktop personal computer equivalent to the results achieved with a CPU cluster.

Multi-objective facility layout problem (mFLP) generates a different layout by varying objectives weights. Since the selection of objective weights in mFLP is critical, stages of designing layout having multiple objectives, the objective weights therefore play an important role in the layout design of mFLP. In practice, it is selected randomly by the layout designer based on his/her past experience that restricts the layout designing process completely designer dependent and thus the layout varies from designer to designer. This paper aims to resolve the issues of selecting the objective weight for each objective. We propose four methods to determine objective weight which makes the design process of mFLP completely designer independent.

In this paper, we are considering the quadratic assignment model (QAP) of the facility layout problem (FLP) which is known to be NP-hard. We relax the integer constraints of the QAP and solve it on a commercially available package called LINGO 8. In the optimal solution so obtained, Xij s take real values between zero and one. We identify promising Xij s having a value strictly greater than 0.5 in the optimal solution and set them to one. We add the constraints (Xij = 1) associated with promising Xij s into the QAP (with integer restrictions) and resolve using LINGO 8. In all the cases attempted we obtained a superior feasible solution to the QAP which was further improved by the proposed modified simulated annealing (MSA) procedure. An encouraging comparative performance of this procedure is thus reported.

This paper describes a heuristic algorithm for solving the plant/facility location problem by applying ant-colony optimization meta-heuristic. The facility location problem is discussed, and a mathematical formulation is presented. The problem is then modelled as a quadratic assignment problem. An ant algorithm is developed to solve the problem. The results reveal that the proposed algorithm can be adaptively constructed to solve discrete plant location problems. This has been applied to a set of known test problems and appears to be able to compete with other current solutions with encouraging results.

Process planning is an important and integral function for ensuring efficient operations in printed circuit card assembly systems. This paper presents a new approach for solving the circuit card to assembly line assignment problem to minimize assembly time. This problem occurs frequently in process planning for electronic assembly systems and involves considering other interelated process planning problems. The line assignment problem is formulated as a large-scale mixed-integer programming problem and then solved using problem decomposition along with the branch-and-bound algorithm. Techniques for improving the solution time are discussed, and the solution approach is demonstrated using industry representative data sets from Lucent Technologies. For the data sets considered, the solution approach provides solutions within 3% of optimal in approximately 6 min of computation time on a Sun UltraSparc 2 Workstation. The solution approach developed for addressing the line assignment problem can serve as a use...

This paper addresses two real-life assignment problems. In both cases, the number of employees to whom tasks should be assigned is significantly greater than the number of tasks. In the simple job ...

SUMMARY Many manufacturing systems require an assignment of machines to locations along a straight track, so as to optimize material flow. This paper uses a cut approach to the corresponding quadratic assignment problem, and derives a heuristic which generates a good solution. In addition, a modified lower bound to the assignment problem is also developed, which is always better than the classical lower bound. Results showing the performance of the heuristic are demonstrated, along with a comparison of the modified and classical lower bound. In almost all the test problems, the solution generated by the heuristic was either optimal or better than any solution obtained by other methods. Extension of the heuristic to more general cases also is considered.

SUMMARY The problem of grouping of parts has been addressed in the past using clustering methods and integer programming. This paper presents an assignment model to solve the grouping problem. A similarity coefficient matrix is used as the input to the assignment problem. Closed loops in the form of subtours are identified after solving the problem and are used as the basis for grouping. The method has been applied to a number of examples. Compared with the earlier mathematical programming model, viz., the p-median model, the assignment method emerges as a distinctly superior technique both in terms of quality of solution and computational time.

The paper deals with the problem of optimization of a quality inspection process structure. The problem is identified with designing an optimal arrangement of inspection operations in a production process (linkages of the quality inspection process with manufacturing and accessory processes). Three mathematical models for the cases of specialized and versatile inspection stations are formulated. It is shown that the problem can be treated as a particular case of a standard assignment problem. An optimization procedure, grounded on Balas' algorithm, is proposed. A numerical example, based on real data, is given.