A reactive algorithm for the hybrid flow shop scheduling problem

Increasing the performance of manufacturing systems is one of the major application areas of operational research. Developed manufacturing systems can produce different products according to the different customer requirements at different times and deliver them with different quantities at different due dates. It is necessary to use resources effectively to run such a complex production system successfully. To plan and operate complex production systems effectively various models and approaches have been developed. Increasing competition, differentiation of customer demands and rising of expectations oblige companies to manage production systems more effectively. Continuously changing conditions and uncertainties in the environment requires developing dynamic decision-making mechanisms. In many production and service systems, operations are made ready after a series of processing units. Often these operations follow the same sequence. The processing environment which the processing units are ordered in series and the operations follow this sequence called as flow shop. m stages flow shop production system is composed of m processing units. If there are more than one processor units at least one stage, then this processing environment is called as a hybrid flow shop production system. Scheduling is a decision-making process which deals with allocation of limited resources. Researchers are usually interested in the standard hybrid flow shop scheduling problem and try to produce the optimum schedule for the generic case of the problem. In the standard form of the hybrid flow shop scheduling problem all jobs and machines are available at time zero. Machines at a given stage are identical. There is no stochasticity in the system, problem data is deterministic and known in advance. However, there are so many sources of uncertainty in real life. Unexpected situations such as machine breakdowns, new incoming orders, order cancellations, due date changes, fluctuations in processing time, material shortage can be encountered at any time. Occurred changes in the production and uncertainty in the system disrupt the planned schedule and may require making changes. In those circumstances, production schedule can be adapted changing conditions dynamically by using reactive algorithms. In this study, a hybrid flow shop production system where jobs arrive randomly is investigated. It is aimed to develop a reactive algorithm to schedule dynamically the hybrid flow shop scheduling problem. Firstly, an extensive literature review is conducted to design an effective scheduling/rescheduling system for a continuously running production environment. It has been seen that there are so many alternative dynamic scheduling approaches such as dispatching rules, exact algorithms, and heuristics in the literature. In many cases the time needed for schedule generation is neglected and the dynamic scheduling problem is solved by dividing the problem static sub-problems. However, in real life, the schedule generation takes time. Depending on the size of the scheduling data, the scheduling method which is applied, the time it takes to perform the scheduling process may be very significant. Our study differs from the ones in the literature in terms of the taking the scheduling process as a whole and the proposed dynamic scheduling system. Scheduling process is considered as a schedule generation and job order realization on shop floor. The proposed approach works completion time based and reflects the elapsed time while schedule generation to the shop floor. In this study, we aimed to develop a reactive algorithm that can produce solutions to the dynamic stochastic hybrid flow shop scheduling problem. It is considered that the scheduling environment is stochastic, and while the algorithm is running, the production system and also the solution quality can be changed at any moment. Alternative solution algorithms for the hybrid flow shop problem in the static and deterministic environment are analyzed. After that, the solution approaches which are generate feasible solutions in a reasonable time for the bigger problem sizes and dynamic environment are investigated. The conducted extensive review revealed that the fact that genetic algorithms (GA) used in dynamic scheduling mostly because of their adaptation skill to the changing environments. So we decided to use a GA to generate schedules for the considered hybrid flow shop scheduling problem. It is aimed to develop a GA to cover the changing production environment instantaneously by using changeable chromosome structure in its population. Firstly the GA solution quality is checked in static environment by using alternative test problems in different sizes. It is investigated that how the GA population is integrated the changing conditions. It is found that using an approach that considers the search process gains which already done before the dynamic situation happened improve the efficiency. In other words, instead of restarting the GA when the dynamic situation happened, the population of the newly started GA is obtained from the final population of the previous GA by adjusting it to the requirements of the new problem. The developed GA is adapted to the designed scheduling system by using an event driven rescheduling policy. New job arrivals or job completions at any stage are chosen to the rescheduling point. To generate schedules dynamically on a continuously running environment the GA is integrated the scheduling process. Separate from the classical GA approaches after the problem changed, it is not needed to wait until the algorithm evolved. Instead of this, the algorithm trusts little but continuous improvements and transfer of search process gains to the new problem after the dynamic situation happened. After the dynamic scheduling system is designed, we focused on how the stochastic environment can be reflected in the scheduling process. Integration of simulation to the solution evaluation module of the proposed GA is investigated. The stochasticity in the environment is reflected to the GA by using random variables as jobs processing times. And fitness calculation of solutions is done by using simulation. To increase the solution quality of the proposed GA, strategy selection and parameter optimization is performed. The performance of the proposed GA in the static environment is compared with CPLEX optimum solutions for small size problems. To analyze the performance of the proposed GA in the deterministic and dynamic environment, simulated annealing (SA) and shortest processing time (SPT) algorithms are used as a benchmark. Parameter optimization is also performed for SA. Both SA and SPT algorithm is integrated to the designed solution generation and schedule realization process. In the same conditions, the three algorithm is compared according to the solution quality and run time. The proposed GA approach yielded better results than others. Replication number of the simulation module while evaluating fitness of solutions in the dynamic stochastic environment is investigated. By using various test problems at different sizes, confidence interval is analyzed for chosen replication numbers. To analyze the proposed GA performance in the dynamic stochastic environment an analysis procedure is proposed. In this procedure a good solution in the dynamic deterministic environment is assumed to be also a good solution for the dynamic stochastic environment. By using alternative test problems, the proposed algorithm performance in the dynamic stochastic environment and in the dynamic deterministic environment is compared. To increase solution quality in the dynamic stochastic environment, replication number and population size are analyzed together without changing total evaluation budget in the algorithm. Increasing the population size and decreasing the replication number strategy gives better solutions. Test results revealed that a good solution in the dynamic deterministic environment is also good solution for the dynamic stochastic environment assumption is verified especially when there is low level stochasticity in the system.