A constraint programming approach to tool allocation and production scheduling in flexible manufacturing systems

Abstract

This paper presents a constraint programming (CP) methodology to deal with the scheduling of flexible manufacturing systems (FMSs). The proposed approach, which consists of both a model and a search strategy, handles several features found in industrial environments, such as limitations on number of tools in the system, lifetime of tools, as well as tool magazine capacity of machines. In addition, it tackles the problem in a integrated way by considering tool planning and allocation, machine assignment, part routing, and task timing decisions altogether in the approach. The formulation, which is able to take into account a variety of objective functions, has been successfully applied to the solution of test problems of various sizes and degrees of difficulty.

Introduction

A current trend in manufacturing plants is to move towards highly flexible production systems that can respond quickly to demand changes and to the processing of a variety of products. FMSs are considered as one of the newest and most important production technologies to efficiently handle today’s changes in market requirements. An FMS is a network of machines interconnected by a material handling system, where a low or medium volume of parts can be manufactured. FMSs are designed to achieve an efficient usage of resources such as machines, tools, and storage places.

The most important components of an FMS are shown in Fig. 1. This system has machines with buffers for work being processed and buffers for pre-processed and finished parts. Machines need tools in order to carry out operations on parts. Tools have a limited lifetime and are grouped by type. The manufacturing environment employs one or more tool instances (copies) of each type and a tool instance requires a given number of tool slots to be placed in the machine–tool magazine. Parts are moved from one machine to another by material handling devices (MHDs).

The physical characteristics of actual manufacturing systems and severe market requirements introduce more constraints than opportunities when formulation and solution of a scheduling problem is pursued. Scheduling and control problems of FMSs are more difficult than those of mass production systems [1]. The main issues associated with scheduling of FMSs are machine loading, part routing, tool planning and allocation, material handling device assignment, and routing as well as task timing problems. Machine loading is defined as the assignment of processing tasks to machines, which have a limited storage capacity in their associated buffers. Part routing fixes a processing route for each of the parts that must be manufactured. A processing route of a given part is the sequence of machines that it must visit successively to have all its required operations executed. Since machines employ tools, which are grouped by type, to carry out the required operations on parts, tool planning establishes the number tools of each type to support the production requirements. Tool allocation concerns assignment of tools of limited life to machines having tool magazines of restricted capacity. Material handling device loading determines allocation of transport tasks to units having a limited transport capacity and transport units routing determines the route that the device has to follow. Finally, the task timing problem deals with the difficulty of determining the start and completion times for each operation (machining, transportation, and/or storage). It is important to note that all of these problems must be handled simultaneously in order to obtain optimal or good quality solutions.

Efficient operation of FMSs is directly related to tool issues. Veeramani et al. [2], Gray et al. [3], and Atan and Pandit [4] have pointed out that the lack of proper attention to tool planning and allocation problems can lead to underutilization of the system. In addition, Mohamed and Bernardo [5] emphasized that an inadequate number of tools results in low machine utilization and an unacceptable level of downtime, leading to decreased FMS productivity. Therefore, both problems, tool planning and allocation, are critical issues associated with the scheduling problem.

The FMS scheduling problem has been tackled by various approaches. The interest in addressing this problem has been motivated by increasing demands to improve efficiency and reduce costs, and on the other hand, challenging inherent complexity associated with this scheduling problem [6]. An analysis of the most important contributions reveals that the majority of the approaches reported in literature decouple the FMS scheduling problem and adopt assumptions that aim at making it tractable. A selective review of some of the main works in which tools appear to be the critical component is given here.

Sarin and Chen [7] presented a MILP formulation for the FMS machine loading and tool allocation problem. The approach aims at finding part routings and allocating appropriate tools at minimum machining cost. Nevertheless, one of its main limitations is that it does not take into account sequencing and timing problems. In addition, it assumes that each operation can be executed in only one machine. Since the resulting model is considerably large in terms of constraints and variables, and consequently hard to solve, Sarin and Chen [7] proposed a solution procedure based on the Lagrangean relaxation and subgradient methods. Thus, this approach required an adaptation of the model and development of a solution methodology.

Atan and Pandit [4] introduced a MILP model for determining the optimal machine allocation and cutting tool assignment when the total number of tools is selected as a performance measure. The approach first considers the machine loading problem, assuming that machines have access to all required tools and, then allocation of tools to machines. Like Sarin and Chen [7], Atan and Pandit [4] did not take into account sequencing and timing problems.

Roh and Kim [8] presented three heuristic approaches for machine loading, tool allocation, and part sequencing problems of an FMS in which each part is assigned to only one machine for its entire processing. The heuristic approaches aim at minimizing the total tardiness.

Subsequently, Atmani and Lashkari [9] presented a MILP model to tackle the machine–tool assignment and operation allocation problems of an FMS in which the limited tool magazine capacity and tool life are taken into account. Contrary to Sarin and Chen [7], these authors considered that a given operation can be assigned to various machines. The formulation pursues minimization of cost of operations, material handling, and set-ups. The resulting approach has one main drawback, which is that large-size MILP formulations are obtained. Performance of the model was evaluated using one example that consists of four parts to be scheduled, requiring three operations at the most, which should be executed in a manufacturing environment with six machines and seven tools.

In turn, Gamila and Motavalli [1] addressed the loading and scheduling problem, while considering machines having tool magazines of limited capacity, as well as tool life, by means of a decomposition approach. They presented a MILP model in order to first solve assignment of part operations and to determine the number of tools and their allocation to machines. As a second step, they employed a very simple heuristic to generate detailed part scheduling. The resulting approach has several disadvantages. One is that machine loading and tool allocation decisions are tackled before addressing scheduling ones. Thus, since the approach does not deal with the problem in a global way, suboptimal solutions are likely to be obtained. Moreover, the approach does not propose any systematic procedure to obtain a solution when the assignment step leads to an infeasible solution. Another drawback is that only one tool instance per each tool type is permitted.

Finally, Chan and Swarnkar [10] developed an ant colony approach to tackle a problem similar to the one considered by Atmani and Lashkari [9]. The approach minimizes various costs such as machining, set-up, and material handling costs. One drawback of this proposal is that the computational performance depends on various parameters that need to be fixed.

As can be seen, several solution methods have been employed to deal with the scheduling problem of FMSs. One approach based on artificial intelligence techniques that has gained increased attention in the last years is constraint programming [11], [12], [13]. It has been very successful in solving problems in different fields such as scheduling, planning, and transportation [12], [13]. This approach has started to be employed by the process system engineering (PSE) community to deal with the scheduling problem of batch processes [14], [15], [16], [17]. More recently, CP has been applied for tackling the scheduling problem of FMSs in which material handling devices (MHDs) represent limiting resources [18]. It is important to note that in most papers, this technique has been used in combination with programming mixed integer (MIP) approaches and it has not almost been evaluated in its pure form.

The goal of this contribution is to overcome some of the limitations of the scheduling approaches reported in the literature. Thus, this paper presents a constraint programming formulation that addresses the scheduling problem of an FMS in a global way, considering tool planning and allocation, operation assignment, part routing, and task timing decisions, altogether in the model. The approach considers various FMS features related to tools such as limited number of tools and tool instances with dissimilar lifetimes. Moreover, it takes into account that machines have tool holders of a limited capacity. The CP approach involves two components: the model itself and a search strategy. The search procedure takes advantage of some domain features. Computational studies are presented for several examples. Since two of them have already been studied [1] a computational comparison can be made.

The remaining sections of this paper are organized as follows. Section 2 describes the scheduling problem under consideration, Section 3 presents an overview of the CP methodology, and Section 4 introduces the CP model for the FMS scheduling problem at hand. One domain-specific search strategy is presented in Section 5. Results corresponding to several case studies are presented in Section 6. Finally, conclusions are pointed out in Section 7.