Flow Shop Scheduling Problem

Flow shop production structure is composed of n stages of processing units, Mi, M2,. .., Mn, in which different jobs pass through in the same sequence (Fig. 3.2). A job j in each stage i is processed for a certain time py. The requirement is to determine the order of processing the n jobs starting at time zero with no interruption in a minimum time span (makespan). 

In this specific problem it is assumed that machines are always available for processing and jobs are ready at the beginning of the planning horizon. It is also assumed that a buffer of unlimited capacity is available between stages to absorb accumulated jobs waiting for a machine to be released. Further assumptions include the following  

This problem is one of the basic flow shop production structures and one of the early mathematically modeled scheduling problems. A Mixed Integer Programming (MIP) model was developed by Wagner [11]. The model (adopted from French [3]) is as follows. 

To insure that exactly one job is scheduled in position k the following must be satisfied. 

---

Daouas, T., Ghedira, K., and Muller, J. (1995), Distributed Flow Shop Scheduling Problem versus Local Optimization, in Proceedings of the First International Conference on Multi-Agent Systems, MIT Press, Cambridge, MA. 

Tsujimura, Y, Park, S., Chang, S., and Gen, M. (1993), An Effective Method for Solving Flow Shop Scheduling Problems with Fuzzy Processing Times, Computers and Industrial Engineering, Vol. 25, pp. 239-242. 

Roeva, O. Real-World Application of Genetic Algorithms. In Tech, Rijeka (2012) Syam, W.P., Al-Harkan, I.M. Comparison of three meta heuristics to optimize hybrid flow shop scheduling problem with parallel machines. In WASET, vol. 62, pp. 271-278 (2010)... 

Dynamic programming is an optimization technique that is particularly well suited for scheduling problems with makespans that are schedule independent, such as, single-machine problems without setups, proportionate flow shops, and problems with till processing times being identical. It can also be applied on scheduling problems with makespans that do depend on the sequence. 

The job shop has a more general structure than the flow shop in which each job go through multiple processing stages (or machines) in an order that might be different than other jobs. The basic job shop scheduling problem holds the same assumptions that were made for the basic flow shop problem. In addition it is assumed that each job may be processed by a machine at most once, i.e., without recirculation. 

DE has been successfiiUy applied in many operational research problems, such as flow shop scheduling, job shop scheduling, and VRP. Some of the applications are briefly reviewed below. 

Scholz-Reiter B, Rekersbrink H, Gorges M (2010b) Dynamic flexible flow shop problems - scheduling heuristics versus autonomous control. CIRP Aim Manufact Technol 59(1) 465 68 SFB (2012) http //www.sfb637.uni-bremen.de/uploads/ pics/folie 3.jpg... 

The most common used notation for theoretical scheduling is the so-called three-field notation introduced by Graham et al. (1979). The notation foresees three fields called a p y. The first field defines the scheduling environment a equal to F stands for flow shop, / for job shop, P for parallel machines, and O for open shop. A number can be inserted to indicate the number of machines. The second field specifies job characteristics indicating, for example, the preemption, ready times, and additional resources. The third field specifies the performance index (objective). Some examples can be the following l Sjk C,nax denotes a single-machine problem with sequence-dependent setup times and minimization of maximum completion time makespan)-, JmWCmax denotes a job-shop problem with m machines an[Pg.1094]

This section explains the formulation of the order scheduling problem in an order-based manufacturing factory. Production processes of each order should be performed in different types of shop floors respectively. Each type of shop floor comprises one or more assembly lines. According to a pre-determined production flow, production processes involved in each order must be completed on an assembly line of the corresponding shop floor. For simplicity, we assume that there is no work in progress (WIP) in each shop floor. 

---