Variability of completion time differences in permutation flow shop scheduling

摘要

Homogeneity of a specific indicator in scheduling has been discussed in several references. Namely, the variance of completion times (completion time variance, CTV) has been addressed by several authors since the 1970ies. However, in contrast to some indications in these papers, CTV does not provide smoothness of jobs' completion times but is more aiming at minimizing the deviation from a common finishing date of all jobs. In this paper, a new objective function is proposed which intends to smooth the differences between the completion times of each two consecutively scheduled jobs in a permutation flow shop setting. We discuss the relevance of respective considerations, define an objective function accordingly and compare some solution approaches by means of examples and a numerical study based on the test instances from Taillard. A main topic of this paper is the discussion of the influence of scheduling decisions on other systems linked to this scheduling system by using our new objective function. This intends to contribute, in a specific and heuristic way, to reduce the gap between the dynamic-stochastic perspective of queuing approaches on one hand and the mostly static-deterministic perspective of job scheduling on the other.