Abstract
This chapter deals with a hybrid flow shop scheduling problem involving sequence dependent setup times, commonly known as the SDST hybrid flow shop, and each stage (work centre) consists of parallel identical machines. In this problem, each job has a different release date and consists of ordered operations that must be processed on machines from different centers in the same order. In addition, the processing times of operations on some machine centers may vary between a minimum and a maximum value depending on the use of a continuously divisible resource. We consider a non-regular optimization criterion based on due dates which are not a priori given or fixed but can be assigned by a decision-maker. A due date assignment cost is also included into the objective function. Finally, the results obtained through the use of GRASP (Greedy Randomized Adaptive Search Procedure) are compared with those computed by SA (Simulated Annealing).
TopIntroduction
There are several flow patterns of scheduling categorized based on the number of operations required to process a job and on the number of available machines per operation and finally number of work centers.
The concept of routing can be introduced based on machines; we have single machine shop, flow shop, permutation flow shop, job shop, and open shop scheduling problems. When processing stages are considered instead of machines, we have parallel machine shop, hybrid flow shop, and job shop with duplicate machines scheduling problems (Gholami, Zandieh, & Alem-Tabriz, 2009). The process industry such as the printed circuit board, automobile, chemical, pharmaceutical, oil, food, tobacco, textile, paper, and metallurgical industries can be modeled as a hybrid flow shop.
The Hybrid Flow Shop (HFS) scheduling problem has been widely discussed in the literature and has many industrial applications. An HFS scheduling problem is an extended form of classical flow shop in which parallel machines are available to perform the same operation. It can be briefly described as follows: a set of jobs has to be processed on a set of processing centers. Each machine centre consists of a set of identical parallel machines, and the non-pre-emptive processing of a job has to be done on exactly one of the machines of each centre. In other words, each job consists of a sequence of operations processed at successive canters and all jobs pass through canters in the same order.
It is apparent that there is a large gap between the literature of scheduling and the real life industry. For instance, many of researchers have ignored setup times or assumed that setup times on each machine are independent of the job sequence (Zandie, Fatemi Ghomi, & Moattar Husseini, 2006). Zandieh et al. (2006) illustrated schematically the relationships between the different machine environments of scheduling problems. A practical assumption of this research is that the Sequence-Dependent Setup Times (SDST) are required when a switch between two different jobs occurs (Naderi, Zandieh, & Roshanaei, 2008). The application of SDST could be seen in many real-life situations such as chemical, printing, pharmaceutical, and automobile manufacturing (Mousavi, Zandieh, & Amiri, 2011).
Pinedo (1995) (3) discussed that machine setup time is a critical factor for production scheduling easily consuming more than 20% of available machine capacity if not well handled. Scheduling problems with sequence-dependent setup times are among the most difficult classes of scheduling problems. Even for a small system, the complexity of this problem is beyond the reach of existing theories (Luh, Gou, Zhang, Nagahora, Tsuji, & Yoneda, 1998).
Sequence-dependent setup scheduling of a hybrid flow shop system is even a challenging issue of hybrid flow shop scheduling problems in which a time lag is defined between the end of the processing of one job at one machine inside one stage and the beginning in the next stage in which the job is processed. Although there has been some progress reported in this field, the understanding of sequence-dependent setups, however, is still believed to be far from being complete (Luh, Gou, Zhang, Nagahora, Tsuji, & Yoneda, 1998).
In many industrial scheduling practices, managers develop schedules based on multi criteria and have to decide the due dates and processing times as parts of scheduling activities. Further, in practical scheduling situations, there are multiple machines in each centre and the objective function often reflects the total cost of processing, earliness and tardiness (Gupta, Kruger, Lauff, Werner, & Sotskov, 2002).
Considering previous comments, we assumed that processing times are not necessarily fixed in advance but can be controlled depending on the use of a continuously divisible resource. Additionally, a release date is given for each job which is the earliest possible starting time for processing this job.
Key Terms in this Chapter
Sequence Dependent Setup Times: Each machine's setup time of a particular job is determined by both that job and the previous job that the machine is currently setup for.
Controllable Processing Times: The processing times of operations on some machine centers may vary between a minimum and a maximum value depending on the use of a continuously divisible resource.
SA: The Simulated Annealing is a probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. Its name comes from annealing in metallurgy. If you heat a solid past melting point and then cool it, the structural properties of the solid depend on the rate of cooling. If the liquid is cooled slowly enough, large crystals will be formed. On the other hand, if the liquid is cooled quickly, the crystals will contain imperfections. The algorithm simulates the cooling process by gradually lowering the temperature of the system until it converges to a steady state.
Assignable Due Date: Due dates which are not a priori given or fixed but can be assigned by a decision-maker.
Hybrid Flow Shop Scheduling (HFS): An HFS scheduling problem is an extended form of classical flow shop in which parallel machines are available to perform the same operation. It can be briefly described as follows: a set of jobs has to be processed on a set of processing centers. Each machine centre consists of a set of identical parallel machines, and the non-pre-emptive processing of a job has to be done on exactly one of the machines of each centre.
NP-Hard Problems: Non-deterministic Polynomial-time Hard, in computational complexity theory, is a class of problems that are, at least as hard as the hardest problems in NP. A problem is NP-hard if an algorithm for solving it can be translated into one for solving any NP-problem (nondeterministic polynomial time) problem.
Grasp: The GRASP (Greedy Randomized Adaptive Search Procedure) metaheuristic is a multi-start or iterative process, in which each iteration consists of two phases: a construction and a local search. The construction phase builds a feasible solution by probabilistically selecting the next element to be incorporated in a partial solution from a restricted candidate list (RCL) composed of the best elements, as measured by a greedy function. Local search is then applied to the constructed solution until a local optimum is found.
Flexible Flow Shop Scheduling (FFS): An FFS scheduling problem is related to a group of parallel machines arranged into a number of stages in series. At each stage, there are number of identical machines in parallel. Each job has not to be processed at each stage and it can ignore one or more stages. Each machine can process at most one job at a time.