## 1 Introduction  
During the last few decades, the Cellular Manufacturing (CM) production philosophy has been implemented with favorable results in many manufacturing firms. According to CM principles, parts requiring similar production processes are grouped in distinct manufacturing cells, made by dedicated clusters of machines. The main advantages connected to the use of CM production strategies usually include reduction of setup and throughput times, simplified material handling, centralization of responsibilities, better quality, and production control [1; 2; 3]. Furthermore, the CM approach also facilitates the adoption of advanced manufacturing technologies, such as computer integrated manufacturing, Just In Time JIT production and flexible manufacturing systems [4]. The design of a Cellular Manufacturing System (CMS) usually starts with the cell formation phase, in which parts are clustered in families and groups of machines are identified; the second step consists in defining the machine layout within each cell and the arrangement of cells with regards to each other; then, a proper schedule concerning part families to be processed at each cell has to be determined; finally, the issue of allocating tools, materials, and human resources to each cell has to be addressed [5]. Due to similarities among their process requirements, parts belonging to the same family generally visit machines in a cell according to the same sequence. Therefore, manufacturing operations within cells often follow a flow-shop scheme [6]. An important benefit of the CM approach actually lies in the fact that even traditional batch or job-shop manufacturing operations may be easily converted in simpler flow-lines [7]. Furthermore, there often exist minor differences in terms of setup requirements among parts belonging to the same family. Notably, each family may be divided into smaller groups made by jobs sharing the same setup operations to be performed on the machines composing the cell [8]. The problem of scheduling jobs in such a manufacturing system is usually referred to as the Flow-Shop Group Scheduling (FSGS) problem. In a classical FSGS problem, a measurable setup is required when switching from one group of parts to another, whereas the setup time between jobs belonging to the same group either is assumed to be negligible or it can be included along with the run time. Therefore, there exists a clear advantage in processing together jobs belonging to the same group, arranging the whole production schedule through subsequent groups. The decision issue to be addressed when facing a FSGS problem is, thus, twofold: the optimal sequence of groups and the optimal sequence of jobs within each group have to be determined with reference to a given performance measure. However, since each feasible solution for a FSGS problem may be described by a simple sequence of jobs passing through each machine belonging to the manufacturing cell, such a problem still remains a permutation scheduling issue, as in classical flow-shops. A pioneer research on the FSGS problem was carried out by [PERSON], [PERSON], and [PERSON] [9], who proposed an optimizing algorithm for minimizing the total completion time in a two-machine group-scheduling problem. A similar issue was addressed by [PERSON] and [PERSON] [10] under the makespan minimization viewpoint. The authors investigated the NP-hardness of such a problem, taking into account blocking effects and anticipatory setups. Two years later, [PERSON], [PERSON] and [PERSON] [11] compared the performances reported by several single-pass and multi-pass heuristic algorithms for minimizing the makespan in FSGS problems with up to 10 machines. The recent research addressing group scheduling issues in flow-shop manufacturing environments has been mainly focused on the Flow-Shop Sequence-Dependent Group Scheduling (FSDGS) problem, in which the time required for performing setup operations of each group of jobs depends on the technological features of the previously processed group.