Critical path analysis for permutation flow shop scheduling problem

Abstract

Scheduling problems in flow shop processes have a great impact on alarge number of applications, both at a production and industrial level,as well as process systems in general (information technologies andbusiness). In all these applications, the most studied objective functionis the makespan, seeking to minimize the total processing time for agiven set of jobs - in its simplest structure (one machine per stage ofthe process, without release date, and no particular conditions for jobprocessing), an NP-Hard problem for 3 machines or more. Within theway of approaching the problem according to the solution category,permutation solutions are the most widely used; in them, the same order of jobs is respected in all process stages. In the literature, thereare a large number of approaches and methods proposed to address theoptimization of the makespan for this problem. This paper proposes tostudy the structure of the solutions from the perspective of the structureof its critical path, considering as a critical path the set of operationssupporting the makespan. In this approach, some results from the literature will be used to extend the solutions to other cases. In turn, thepotential impacts of considering the solution structure for the design ofsolving methods will be presented and discussed.