A meta-heuristic approach for solving flexible flow-shop and job-shop scheduling problems

Abstract

The present day manufacturing industries face the external challenges like changes in market demand, customized products, shorter product life cycle and competition in the market. The manufacturing industries also face internal challenges like job fluctuations (job cancellations and sudden job arrivals) and internal uncertainties (uncertainties in processing time, tool failure, machine breakdown). To tackle these challenges in manufacturing industries, especially in shop floors, operations research community focused in last few decades on finding optimal schedules to allocate various jobs to different machines. In manufacturing sector, good scheduling strategies help the industries to compete and survive in the market place. Manufacturing industries have deadlines (called due dates) committed to customers. Failure to deliver the products within the due dates results in the loss of goodwill of the manufacturing firm. Therefore, scheduling is an important decision making strategy, which directly affects not only the profit of the industry but also the good will among its customers. Scheduling is defined as the process of allocating scarce resources to the activities with an objective to optimize one or more performance measures like makespan, flowtime, tardiness, total workload, critical workload etc.
Based on the manufacturing processes, scheduling problems can be categorized into flow-shop, job-shop, flexible flow-shop and flexible job-shop. Among these, flexible flow-shop and flexible job-shop are strongly NP-hard problems. In the pursuit of solving scheduling problem, some assumptions are made. They are (i) setup time is negligible or setup time is included in the processing time, (ii) there is no machine breakdown during the entire scheduling period and (iii) processing time is deterministic and known in advance. These assumptions seem to be less practical in real practice. Moreover, most of research on scheduling is devoted on minimization of a single objective like makespan. In order to generate schedules that are more useful to real world shop floors, uncertainty that arise in a shop floor should be taken into consideration.
Even though the exact methods guarantee optimal solution, they fail to solve large size problems. On the other hand, heuristic techniques are capable of handling the large size problems but they are problem dependent and likely to be stuck up at local optimum. To overcome the limitations of exact and heuristic methods, research focus is shifted to meta-heuristic techniques which provide realistic solutions for complex scheduling problems. During the last decades, many meta-heuristic techniques have been applied to solve various engineering optimization problems. Some of the popular meta-heuristic techniques are genetic algorithm (GA), tabu search (TS), simulated annealing (SA), artificial immune system (AIS), ant colony optimization (ACO), fire fly algorithm (FFA), bat algorithm (BA), particle swarm optimization (PSO), harmony search (HS). All these algorithms have one thing in common i.e. they have algorithm-specific tuning parameters. Without proper tuning of these parameters, it is difficult to obtain optimal solution.
Therefore, in the present work, research has been focused on recent meta-heuristic technique called teaching-learning-based optimization (TLBO) because it does not have any algorithm-specific tuning parameters. As tuning the parameters is a difficult task, this drawback can be eliminated by using TLBO. Unlike other algorithms, parameter-less feature of TLBO eliminates the drawback of solving the NP-hard flow-shop scheduling problem (FFSP) and flexible job-shop scheduling problem (FJSP) again and again until the right kind of tuning parameters are found. Apart from this, a new local search technique is proposed in this work to increase the efficiency of basic TLBO algorithm. The present research work begins with the general objective of makespan minimization and later uncertainties that arise in the real world shop floors are dealt. They are uncertainty in processing time, machine breakdown and sequence-dependent setup time with machine breakdown. Also, a multi-objective optimization of contradistinctive and conflicting natured objectives (i.e. makespan and mean flowtime) is studied using TLBO. From results, it is found that TLBO is one of the competitive algorithms that can be applied to solve FFSP and FJSP.