A Non-Permutation Flow Shop Manufacturing Cell Scheduling Problem with Part's Sequence Dependent Family Setup Times

A Non-Permutation Flow Shop Manufacturing Cell Scheduling Problem with Part's Sequence Dependent Family Setup Times

Behzad Nikjo, Yaser Zarook
Copyright: © 2014 |Pages: 17
DOI: 10.4018/ijamc.2014100104
(Individual Articles)
No Current Special Offers


This article presents a new mathematical model for a dynamic flow shop manufacturing cell scheduling problem (DFMCSP) with agreeable job release date for each part family where family setup times are dependent on sequence of parts within families. It means this article considers non-permutation schedules for both sequence of families and sequence of parts within families. The objective is minimizing the Makespan (Cmax). Since, this problem belongs to NP-Hard class. Therefore, reaching an optimal solution in a reasonable computational time by using exact methods is extremely difficult. Thus, this article proposes meta-heuristic methods such as Genetic Algorithms (GA) and Tabu Search (TS). Finally, the computational results compare efficiency of the proposed algorithms under the performance measures.
Article Preview

1. Introduction And Literature Review

Cellular Manufacturing (CM) is one of the most important applications of group technology. Relevant studies have found that CM has many advantages, including shortened setup times, reduced work-in-process (WIP), less material handling and simplified production planning and control (Chen, 1995). Due to the wide applications of CM, the manufacturing cell scheduling problem (MCSP) has become a matter of great concern in the field of scheduling. MCSP is classified into two groups (Billo, 1998): job shop environment and flow shop environment. In job shop cell, we have low part similarity where materials follow irregular pattern, this environment is more flexible. In flow shop cell, usually, we have more simplified product flows due to the higher part similarity, in this case materials follow linear pattern. On other words, each job within a part family is processed on each machine in the same technological order; this is called a flow-line (or flow-shop) manufacturing cell (Bouabda et al., 2011). MCSPs are concerned with sequencing part families and parts within families where each MC is dedicated to producing a specific number of part families. Since, the parts are assigned to part families based on similar characteristics and operation requirements, in practice, it is quite often the case that prior to processing each part family, major sequence dependent family setup times (SDFSTs) will arise on each machine. The FMCSP with SDFSTs has an abundance of implications in many industries, In view of these broad applications; researchers have developed efficient algorithms to solve it. A structure of this problem is displayed in Figure 1.

Figure 1.

Illustration of the flowshop manufacturing cell


Although, optimal solutions can be obtained via exact methods such as the procedures that were proposed by Das and Canel (2005); Gupta and Schaller (2006). Most FMCSPs with SDFSTs found in industries are sufficiently large so as to preclude the use of exact methods. Therefore, those exact methods require considerable computational efforts and they can’t solve problems with realistic sizes. The formidable computational requirements have forced researchers and practitioners frequently seeking approximation algorithms that generate near-optimum solutions with relatively little computational expense (Frazier, 1996; Schaller et al., 2000; Logendran et al., 2005). Recently, meta-heuristic based algorithms that can consistently produce (near-) optimum solutions for a variety of large scale combinatorial optimization problems have become a growing force in improvement heuristics. In the literature, many Meta-heuristic based algorithms are established for solving the Fm| fmls, Si i’| Cmax problem and FMCSPs with different configurations include those based on memetic algorithms (França et al., 2005; Ying et al., 2012), genetic algorithms (França et al., 2005; Lin, Gupta, et al., 2009), Tabu search (TS) algorithms (Hendizadeh, Faramarzi, Mansouri, Gupta, & ElMekkawy, 2008; Lin, Gupta, et al., 2009; Logendran, deSzoeke, & Barnard, 2006; Logendran, Salmasi, & Sriskandarajah, 2006), and simulated annealing (SA) algorithms (Lin, Gupta, et al., 2009; Lin, Ying, & Lee, 2009; Ying et al., 2010; Lin et al., 2011). In addition to permutation schedule researches, there are another group of studies as non-permutation schedule (NPS) on FMCSPs. Related works, Lin, Ying & Lee (2009) considered meta-heuristics as GA, SA and TS for FMCSPs with SDFSTs. Ying (2008) have proposed an effective iterated greedy algorithm for solving non-permutation flowshop scheduling problems. Ying et al. (2010) have addressed permutation and non-permutation schedules for the flowline manufacturing cell with sequence dependent family setups and solving them by simulation annealing.

Complete Article List

Search this Journal:
Volume 15: 1 Issue (2024)
Volume 14: 1 Issue (2023)
Volume 13: 4 Issues (2022): 2 Released, 2 Forthcoming
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing