Scheduling with Uncertain Processing and Setup Times

The first scientific work on flowshop scheduling problems was conducted by Johnson (1954). Since then, the flowshop scheduling problem has attracted considerable attention from researchers and hundreds of papers have been published in scheduling related journals. The vast majority of research on the problem assumes that job processing times are known fixed values in advance. In other words, the precise information about how long each job will take on each machine is available. It is true that there are many problems in real life where job processing times can be modeled as known fixed values. On the other hand, it is not realistic to assume they are known fixed values for some other scheduling problems. For such scheduling environments, job processing times are unknown variables and the only information that can be obtained is about lower and upper bounds for each job, which may be called, bounded processing times. The two machine flowshop scheduling problem with bounded processing times was addressed by Allahverdi and Sotskov (2003) to minimize makespan. The same problem but with total completion time criterion was studied by Sotskov et al. (2004). Setup times were ignored by both Allahverdi and Sotskov (2003), and Sotskov et al. (2004). The assumption of including setup times in processing times is a common assumption in the flowshop scheduling research. While this assumption may be justified for some real scheduling problems, other situations call for explicit setup time consideration. For example, the production of seamless steel tube in iron and steel industries (Tang and Huang, 2005) or group scheduling in flexible flowshops (Logendran et al., 2005). The practical situations in which setup times must be considered as separate include chemical, pharmaceutical, printing, food processing, metal processing, and semiconductor industries, see Allahverdi et al. (1999, 2007) for surveys on scheduling problems with separate setup times. The performance measure may be improved by considering setup times as separate from processing times.