Universality of Makespan in Flowshop Scheduling Problem

Makespan, which is defined as the time difference between the starting time and the terminate time of a sequence of jobs or tasks, as the time to traverse a belt conveyor system, is well known as one of the most important criteria in scheduling problems. It is often used by manufacturing firms in practice in order to improve the operational efficiency with respect to the order of job processing to be performed. It is known that the performance of a machine depends on the particular timing of the job processing even if the job processing order is fixed. That is, the performance of a system with respect to flowshop processing depends on the procedure of scheduling. In this present work, we first discuss the relationship between makespan and several scheduling procedures in detail by using a small example and provide an algorithm for deriving the makespan. Using our proposed algorithm, several numerical experiments are examined so as to reveal the relationship between the typical behavior of makespan and the position of the fiducial machine, with respect to several distinguished distributions of the processing time. We also discuss the behavior of makespan by using the properties of the shape functions used in the context of percolation theory. Our contributions are firstly giving a detail discussion on the universality of makespan in flowshop problems and obtaining several novel properties of makespan, as follows: (1) makespan possesses universality in the sense of being little affected by a change in the probability distribution of the processing time, (2) makespan can be decomposed into the sum of two shape functions, and (3) makespan is less affected by the dispatching rule than by the scheduling procedure.