Alternative Heuristic Algorithm for Flow Shop Scheduling Problem

Introduction

The main problems in scheduling of jobs in a manufacturing cell are, according to Wight (1984), “priorities” and “capacity”. Hejazi and Saghafian (2005) characterize scheduling problem as an effort to specify the order and timing of the processing of the jobs on machines, with an objective or objectives respecting above-mentioned assumptions“. Henry Gantt, as the inventor of the now well-known Gantt chart, and Frederick Taylor, with his theories of Scientific Management, give the first scientific consideration to production scheduling. Computer-based production scheduling systems that emerged later were mostly connected to the shop floor tracking systems and used dispatching rules to sequence the work (Herrmann, 2006). Such computer aided scheduling systems are now being integrated in manufacturing execution systems. Similar solutions of scheduling systems are now part of ERP systems that was performed in the early 1990s. Manufacturing execution systems besides their typical functions were developed and used also as the interface between ERP and process control (Modrák, 2009).

The scheduling that is related to cellular manufacturing systems is known as operation scheduling or shop scheduling. According to Cox et al. (1992), this type of scheduling is aimed to find “the actual assignment of starting and/or completion dates to operations or groups of operations to show when these must be done if the manufacturing order is to be completed on time.” The scheduling of cellular manufacturing systems (CMSs) is also known as “group scheduling”. Its importance has long been recognized as critical the successful implementation of Group Technology (Mosier, et al., 1984, Ruben and Mahmoodi, 1999). Existing research efforts in group scheduling can be classified in two groups: those that consider a single cell and those that consider multiple cells (Hendizadeh et al., 2008). This chapter is concerned with multi machine Flow Shop Scheduling Problems (FSPs) that present a class of Group Shop Scheduling Problems in which the operations of every job have to be processed on m machines in this same order. Johnson (1954) has shown that, in a 2-machine flow shop, an optimal sequence can be constructed. It was demonstrated later that m-machine flow shop scheduling problem (FSP) is strongly NP-hard for m≥3 (Garey et al., 1976, Lenstra et al., 1977). The criterion of optimality in a flow shop sequencing problem is usually specified as minimization of make-span that is defined as the total time to ensure that all jobs are completed on all machines. If there are no release times for the jobs then the total completion time equals the total flow time. In some cases for calculating the completion times specific constraints are assumed. For example, such a situation in the FSP arises when no idle time is allowed at machines. This constraint creates an important practical situation that arises when expensive machinery is employed (Chakraborty, 2009). The general scheduling problem for a classical shop flow gives rise to (n!)^m possible schedules. With aim to reduce the number of possible schedules it is reasonable to make assumption that all machines process jobs in the same order (Gupta 1975). In the classical flow-shop scheduling problem, queues of jobs are allowed at any of m machines in processing sequence based on assumption that jobs may wait on or between the machines (Allahverdi et al., 1999). The proposed alternative algorithm for minimizing completion time is assumed for a static-deterministic permutation flow shop scheduling problem (PFSP) with n jobs and m machines. In this chapter, the objective function for the PFSS problem corresponds to the minimization of the make-span when idle time is allowed on machines.