DEVELOPMENT AND EVALUATION OF APPROXIMATE ALGORITHMS FOR DISTRIBUTED PERMUTATION FLOWSHOP SCHEDULING PROBLEM

Abstract

Scheduling is a way of making decisions that occurs on a regular basis in various manufacturing and services industries. It is about figuring out how to best use resources for different tasks over specific periods of time, with an aim to optimize one or more objectives. These resources and tasks can be all sorts of things. Resources may be machines in a factory, runways at an airport, workers on a construction site, computers in an office, and more. Tasks can be things like operations in making a product, planes taking off and landing, stages in building a project, executions of computer programs, and so on. Each task may have its own priority level, a time when it should ideally start, and a deadline for when it needs to be finished. Also, the objectives can have different forms in scheduling problems. For instance, one may aim to finish the last task as early as possible, or one can focus on reducing the number of tasks that are finished late. Scheduling, as a decision-making process, plays an important role in most manufacturing and production systems. It's also crucial for transportation, like planning routes for trucks, and in service industries, like making sure appointments happen on time. The permutation flowshop scheduling problem (PFSP) is a well-known scheduling problem. It has extensive applications in the manufacturing and production industries, which makes it a popular research area. In PFSP, a set of machines are arranged in series, and each job need to visit each machine in the same order in which they are placed. The task is to find a job sequence to minimize the given objective. With the large-scale manufacturing companies shifting towards multi-factory operations, there is a growing need for effective scheduling algorithms. This shift is motivated by factors such as lower management risk, reduced production costs, and delivering high-quality products. Realizing the real-world application need, in the year 2010, Naderi and Ruiz introduced the distributed permutation flowshop scheduling problem (DPFSP), which is a generalization of the conventional PFSP to multi-factory environment. In DPFSP, there are more than one identical factories such that each factory represents a permutation flowshop. The problem involves two tasks. One is to assign the given jobs to factories while the other is to determine the job processing sequence in each factory to optimize specific objective. In most studies, the main goals for optimization include reducing makespan, total flowtime, and total tardiness. However, in this thesis, we focus on total flowtime and total tardiness criteria, which are relevant but received less attention in existing literature. Since, the DPFSP is known to be NP-hard, the traditional methods such as integer programming, branch and bound, etc. can only solve small-scale problems efficiently. For larger distributed scheduling problems, approximate algorithms such as heuristics and metaheuristics are generally considered. These methods can provide optimal or near-optimal solutions within a reasonable computational time. Several promising approaches and methods are proposed in the literature to solve the DPFSP. However, in this thesis, we focus exclusively on the constructive heuristics which can produce better solutions for large-scale DPFSP in few seconds. Constructive heuristics build a solution from scratch by repeatedly extending the current solution until a complete solution is reached. This thesis comprises of five chapter which are as follows: Chapter 1 is introductory in nature and provides the motivation of the work presented along with the objectives and outline of the thesis. Chapter 2 provides the background, basic definitions and preliminary concepts related to DPFSP. Further, the survey on the different approximate solution approaches proposed in literature to solve DPFSP is conducted. Chapter 3 presented an improved constructive heuristic for the distributed permutation flowshop scheduling problem to minimize the total flowtime criterion. Chapter 4 proposes an effective and efficient constructive heuristic for the distributed permutation flowshop scheduling problem to minimize total tardiness criterion. Chapter 5 summarizes the work, presents important conclusions, and discusses the future research directions.