یک ساختار جدید داده ها جهت ارائه راه حل در بهینه سازی ترکیبی کلونی مورچه ها برای مسائل چیدمان تأسیسات پویای بزرگ

A dynamic facility layout problem (DFLP) is concerned with finding a set of facility layouts across multiple time periods that minimizes the total cost of material flows and rearrangement costs. Unlike other heuristic approaches that focus mainly on the searching aspect, this research takes another approach by streamlining the data structure of solution representation to improve the solution swapping and storing activities within a meta-heuristic framework. The experimental results from testing the data encoding and decoding schemes on a DFLP data set have been quite promising in terms of solution quality and computational time.

In today's rapidly changing corporate environments manufacturing facilities are going through periods of expansion and decline due to ever-moving business goals. Fast switching from one product line to another and discontinuing existing production lines is often the norm especially in the high-tech industries. To keep up with the pace, the facility layout needs to be adaptable to changes. The layout has to be “flexible enough to accommodate changes in product design, process design, and schedule design” (Tompkins et al., 2003). Heragu predicted that redesigning existing facilities will become more common than generating new facility layouts in future facility planning (Heragu, 1997). Traditionally, researches into the facility layout problems treat all the data—the departments, areas and flows—as constant. This type of research problems is referred to as the Static Facility Layout Problem or SFLP. Recently, researches into ever-changing facilities layouts known as the Dynamic Facility Layout Problem (DFLP) have generated much interest. Unlike the traditional static facility layout where the layout is relatively constant throughout time, the concept of dynamic facility layout introduces the time dimension into the facility layout planning. To construct a dynamic facility layout, the facility planners or managers must take the time periods into account. At each time period, planners need to consider the material flow cost and rearrangement cost and evaluate whether the facility rearrangement is necessary. Therefore, the pre-determination of material flow costs is required in the dynamic facility layout. Several factors need be considered regarding the dynamic facility layout: (1) the cost incurred due to loss in production time; (2) the costs of physically moving equipments from their existing locations to new locations: planning, dismantling, construction, movement and installation (Kochhar and Heragu, 1999). The dynamic facility layout problem represents one type of combinatorial optimization problems since a dynamic facility layout may have (n!)t combinations for a given n departments, t periods. Many heuristic or meta-heuristic approaches to solve the DFLP may involve a significant amount of swapping and storing of candidate solutions in quest of local and global solutions. In another word, by improving solution swapping and storing may lead to a significant reduction of computational time and memory space, especially with large combinatorial optimization problems. Consider a 30-department, 10-period dynamic facility layout problem—the amount of memory it takes for a single DFLP solution is: View the MathML source30departments×4bytes(integerdatatype)×10periods=1200bytesor300integers(basedonaVisualC++program) Turn MathJax on On the contrary, each department can be represented by only 1 byte: View the MathML source30departments×1byte=30bytes÷4bytes(integerdatatype)≅8integers8integers×10periods=80integers Turn MathJax on The encoding results in a 4-fold data storage improvement. Additionally, several nominal values may be packed into one 32-bit integer type: for 8-department and 15-department layouts, 4 nominal values are packed into an integer while 30-departments 2 nominal values are packed. With a more compacted data structure and less bytes to manipulate, the author theorizes that a shorter computational time can be achieved for the solution swapping, which is a major activity in local and global searches of meta-heuristics. Therefore, this author considers improving the computational efficiency by focusing on the data structure of solution representation. Inspired by data encoding in telecommunication systems, the author investigates encoding the solution representation in DFLP to pack as much solution representation as possible into as few bits or bytes as possible. The author proposes two Binary Coded Hybrid Ant Systems (BC-HAS), modifications of HAS I and HAS III presented by McKendall and Shang (2006) to solve the dynamic facility layout problem using encoding and decoding schemes. This paper is organized as the follows: In the next section, the author presents the background and relevant information on the dynamic facility layout. In Section 3 the meta-heuristic framework, ant colony optimization, is discussed along with solution encoding/decoding schemes for solving the DFLP. In Section 4 the newly proposed heuristics are compared with existing approaches to the DFLP and the results are presented. Finally, the conclusion is given in Section 5.

In this paper the author has proposed encoding and decoding schemes for solution representation within a meta-heuristic framework. Additionally, the swapping scheme as well as department rearrangement determination scheme have also been developed. The proposed encoding and decoding schemes for hybrid ant colony optimization have achieved the following objectives for heuristics as prescribed in (Barr et al., 1995): • Fastness—benchmarked with other heuristics, the encoding and decoding schemes have shown great reduction on computational time—it outperforms other benchmarked heuristics by more than 3 or even 8 times faster on large 30-department, 10-period DFLP problems. • Robustness—the proposed encoding/decoding schemes have improved the solution quality for each large size problem (30 departments) in the problem set. • Simplicity—the encoding and decoding schemes are simple to implement with an understanding of bitwise manipulation. • Generalization—because the encoding/decoding schemes impact only the data structure aspect of the meta-heuristics, encoding and decoding schemes can be easily incorporated into other meta-heuristics to represent solutions for other types of combinatorial optimization problems such as cities in TSP and nodes in VRP and improve local and global swapping, which make up a significant amount of activities in other meta-heuristics such as Particle Swarm Optimization and Simulated Annealing as well. • Innovation—this research uniquely focuses on the data structure of solution representation for meta-heuristics, which has not been much researched in existing literatures. With the experimental results, the author concludes the data structure of solution representation has a significant impact on the computational efficiency of heuristics in terms of computational time and memory space. Therefore, hopefully, the finding will stimulate more research studies into this field. For future researches, other factors—potentially important under some circumstances—will be considered. Some other considerations potentially influencing DFLP are multi-floor layout for regions with severely constrained land mass, fluctuating product demand or product mix and the rolling facility planning horizon (i.e., facility planning horizon that is continuously expanding).