Changeover Times and Transportation Times

In this chapter we consider scheduling problems in which the set I of all jobs or all operations (in connection with shop problems) is partitioned into disjoint sets I_l,... , I _r called groups, i.e. I = I_l ∪ I₂ ∪ ... ∪ I _r and I _f ∩ I _g = Ø for f, g ∈ {1,... , r},f ≠ g. Let N _j be the number of jobs in I _j . Furthermore, we have the additional restrictions that for any two jobs (operations) i, j with i ∈ I _f and j ∈ I _g to be processed on the same machine M _k , job (operation) j cannot be started until s _fgk time units after the finishing time of job (operation) i, or job (operation) i cannot be started until s _gfk time units after the finishing time of job (operation) j. In a typical application, the groups correspond to different types of jobs (operations) and s _fgk may be interpreted as a machine dependent changeover time. During the changeover period, the machine cannot process another job. We assume that s _fgk = 0 for all f, g ∈ {1,... ,r}, k ∈ {1,... , m} with f = g,and that the triangle inequality holds:9.1 $${s_{fgk}} + {s_{fhk}}{s_{fhk}}\,for\,all\,f,g,h \in \{ 1,...,r\} ,k \in \{ 1,...,m\} .$$