Irohara Takashi

In this paper, we propose a heuristic algorithm for unrelated parallel machine scheduling problems. In an unrelated parallel machine, there is no particular relationship among processing times for each job since they are different depending on the machine. The processing times for the jobs assigned to one machine are not proportional to the processing times that correspond to another. The objective function is to minimize the total weighted tardiness and earliness for each job. An unrelated parallel machine scheduling problem can be divided into two problems: one is the assignment problem, which is to assign the jobs to machine types; and the other is the scheduling problem, which is to schedule the jobs on each machine type. In the proposed method, the former problem is solved by making a random initial solution at first. In the latter problem, we apply the Lagrangian decomposition and coordination method to each machine type. In the relaxed problem using the Lagrangian decomposition and coordination method, the machine capacity constraints are relaxed and the optimal values of the Lagrangian multipliers are searched by solving the Lagrangian dual problem using a subgradient algorithm. Then we solve the former problem again using the Lagrangian multiplier. The Lagrangian multiplier helps to solve the former problem because it represents the degree of congestion of jobs on the term. The series of operations is iterated to search for better solutions. Finally, computational experiments show that this approach can find better solutions than the comparative method based on Genetic Algorithm in various environments.

We propose a new approach to optimize facility layout and buffer space allocation for production systems with a feed-forward configuration and variable processing times. Our objective is to efficiently find Pareto-optimal solutions for both throughput and material handling cost. We assume that work transfer is performed by conveyor belt or unlimited vehicles. Since the facility layout does not affect the throughput under these assumptions, we first calculate the throughput for every buffer space allocation using Markov analysis. Then the set of Pareto optimal facility layouts and buffer space allocations is searched using a genetic algorithm. Numerical examples illustrate the proposed approach.

The facility layout problem (FLP) is defined as needing to find an optimal layout with respect to the minimization of material handling costs (MHC) between departments. An elevator (ELV) is a necessity for multi-floor FLPs in order to transfer materials between departments on different floors, and the ELV location significantly influences MHC. While there are some multi-floor layout techniques that consider the ELV location, they have many problems. For example, there is a technique where the ELV is located within a department. In this paper, a new multi-floor facility layout technique is proposed, in which the detailed locations of input/output (I/O) points are determined in addition to departments and ELVs, using an integrated approach of combinatorial optimization and mathematical programming. In this technique, ELVs can be located in free positions without overlapping with departments. I/O points are also optimized within a defined range, but not using conventional ways. The proposed algorithm is based on Simulated Annealing. The objective function is the minimization of MHC between the I/O points of departments along the aisle with the shortest distance. The results of computational experiments show the effectiveness of the proposed algorithm.

It is generally known that the facility layout problem (FLP) is to find an optimal layout with respect to the minimization of material handling costs (MHC) between departments. In most studies on FLP, the existence of aisles and I/O locations in each department are ignored. While there are some layout techniques that consider the aisle structure and I/O location, they have many problems. There are not any techniques that consider the I/O type of a department. Additionally in most studies, the FLP is modeled as a combinatorial optimization problem. When solving a FLP model, only the relative location of departments, aisles and I/O can be decided, not a detailed layout. In this paper, a new layout design methodology is proposed, in which a detailed layout including the aisle structure and I/O locations of departments can be decided using the hybrid approach of combinatorial optimization and mathematical programming approaches. In addition, a new layout expression is proposed based on a revised location matrix that enables one to consider not only the guillotine-cut type layout but also the spiral type layout. The proposed algorithm is based on Simulated Annealing combined with some local search. The objective function is the minimization of materials handling cost between the I/O points of departments along the aisle with the shortest distance. The results of computational experiments show the effectiveness of the proposed algorithm.

In this paper, a new layout expression based on the location matrix and some heuristics are proposed for the determination of aisle structure and I/O locations of each department in a facility layout problem. The proposed genetic algorithm-based algorithm finds multiple solutions along the Pareto optimal frontier. The objective here is to minimize (1) material handling cost and (2) building area. The material movements assume that they are transferred along the shortest distance aisle between the I/O locations of those departments. The results of computational experiments show the effectiveness of the proposed algorithm.

The design of the physical layout is the most important issue to be considered in the early stages of manufacturing system design. Operating costs and system efficiency are significantly affected by material handling. Generally, the facility layout problem is to find an optimal layout with respect to minimizing material handling costs between departments. In most existing studies on the problem, the distance between departments is assumed to be the rectilinear distance between the centers of the departments. Those approaches ignore the existence of aisle and I/O points in each department. A new design methodology for the facility layout problem is presented in this paper. Our objective is to minimize the penalty for the redundant aisle areas and irregular shapes of departments, besides material handling costs. The material movements assume that they are transferred along the shortest aisles between the I/O points of those departments. In this paper, a new layout expression based on location matrix and some heuristics are proposed for determining aisle structure and I/O points. In the new layout expression, the I/O points of each department are located according to intradepartment material flows. We develop an improvement-type layout algorithm based on simulated annealing. In this paper, we propose a new design methodology for the facility layout problem that considers the aisle structure and I/O points of each department. There are three types of I/O points (U, L and I type) and they are decided to minimize the objective while maintaining access to the aisle. Experimental results show that our approach performs quite well for the minimization of material handling costs and the aisle areas.

We propose a new framework of facility layout problems which takes the production efficiency into account explicitly. In the classical framework of facility layout problems, layouts are evaluated only by the material handling cost, and any aspects as to how layouts affect the production efficiencies are not considered. In real systems, however, the layout of facilities do affect the production efficiencies such as throughput, lead time and so on. Thus, in general, there should exist the "best" layout which absorbs the variability involved in the system and attains the highest production efficiency. In short, our problem is to find the layout of facilities which results in the maximal production efficiency. We refer this type of layout problems as the "Stochastic Facility Layout Problem (SFLP)". In this paper, we present an example of SFLP which finds an optimal combination of the facility layout and the buffer space allocation to achieve the maximal throughput. In case when the physical size of a buffer space can not be ignored compared with the facility itself, allocating buffer spaces to a facility affects the distances between facilities. In such a case, the production efficiency (throughput, say) depends on both buffer space allocation and facility layout in a complex way. Our problem gives rational solutions for such a situation. Through this example problem, we discuss the merits and the demerits of SFLP compared with the classical facility layout problems.

In this paper, a new type of Vehicle Routing Problem in which distribution centers exist between factories and customers, is addressed. Each distribution center has no fixed category, which means all customers can be served from any distribution center. When demands occur, products are transported from factories to distribution centers by large fleets, and distributed to customers by small fleets. This results in an inter-dependent relationship between transportation and distribution. However, to take into consideration both transportation from factories to distribution centers and distribution from distribution centers to customers, the solution space becomes extremely large. Thus, it is utterly impracticable to solve the problem by using optimization. This paper, therefore, proposes an integrated heuristic using Tabu Search and Simulated Annealing with two-phase approaches to solve the problem. Numerical experiments has been carried out to demonstrate an effectiveness of the proposed technique.

In this paper, we proposed a hybrid genetic algorithm (Hybrid GA) approach to a multi-objective vehicle routing problem (MVRP). The objective functions considered in this MVRP are (1). to minimize the number of vehicles used, (2). to minimize the total traveling distance for vehicles, (3). to minimize the total waiting time for vehicles, and (4). to maximize the grade of customer satisfaction with due-time. With respect to customer satisfaction with due-time, we used the concept of fuzzy due-time because it can describe customers' preference with service time better than crisped expression of satisfaction with 0 and 1. To handle such multi-objectivity, a set of Pareto optimal solutions are searched by Hybrid GA. Among Pareto optimal solutions, we furthermore targeted at compromise solutions whose objective functions take almost intermediate values each, in order to produce realistic routing plans for vehicles. In the proposed algorithm, a local search procedure is applied to each solution at each generation for efficient search of solutions. The computational results show that the proposed algorithm is efficient for solving MVRP.

In this paper, we address the issue of a cellular munufacturing system layout design, which, in essence, consists of two main problems, cell formation and cell layout, While a number of studies have been conducted on this issue, the two problems were usually considered sequentially, and the impact of cell layout was ignored when solving cell formation. Moreover, it was often assumed that all cells are equal in area and shape, which is not practical for industry-scaled problems. We propose an integrated approach using the Genetic Algorithm (GA) to solve the problems simultaneously, with an assumption that not all cell areas and shapes are equal. Our numerical experiments and results show that our method performs better compared to a conventional method in which cell formation and cell layout are considered sequentially.

Automated Guided Vehicle systems (AGVs) are important in modern manufacturing systems. One of the important issues in the design of AGVs is to determine the direction of AGV, which is known as AGV flow path design problem. Though a number of significant research has been conducted on this problem, most of them do not take into consideration the effect of machine layout when designing AGV flow path. In this paper, an integrated technique employing Genetic Algorithm (GA) and Simulated Annealing (SA) to solve AGV flow path design problem is proposed. GA is used to search for AGV flow path direction, while SA is simultaneously used to search for machine layout.