1 Introduction
-
Setup operations of resources to be altered between two successive jobs can be executed in parallel, so that the maximum time over all current resource setups is to be considered, or sequentially, so that the sum of single resource setups constitutes the setup time.
-
While we always consider operations equipping the machine with a resource type, removal operations caused by removing the resource type required by the previous job may be relevant or not.
-
Setup times per resource can all be equal, e.g., changing any type of exterior steel coil, interior steel coil, and PU cartridge always takes the same amount of time, characteristic-dependent, e.g., changing any type of exterior steel coil takes identical setup time, which may, however, differ from the constant setup time for changing any type of PU cartridges, or value-dependent, e.g., each specific type of steel coil and PU cartridge may require a different setup time.
2 Problem definition and classification
\(v_{j,c}\) | 1 | 2 | 3 |
---|---|---|---|
\(c_1\) | 1 | 2 | 2 |
\(c_2\) | 3 | 3 | 4 |
\(V_{c_1}\)
|
\(V_{c_2}\)
| |||
---|---|---|---|---|
1 | 2 | 3 | 4 | |
\(s^e_{v,c}\)
| 1 | 1 | 1 | 3 |
\(s^r_{v,c}\)
| 4 | 3 | 2 | 4 |
-
Setup aggregation Our first distinction addresses the aggregation of setup times required for altering the divergent characteristics of two successive jobs. Here, we distinguish the two problem versions ModSetup-Seq (e.g., a single worker executes all setups for the different characteristics sequentially) and ModSetup-Par (e.g., each characteristic is serviced by a separate worker, so that all relevant setups are executed in parallel) elaborated above.
-
Removing time Furthermore, we distinguish whether or not there are special setup times for removing values from characteristics required by the previous job. An extra removing time is to be considered, for instance, if removing the steel coils required by the previous jobs takes different amounts of time, e.g., due to varying weights or sizes. Once all removing times for the different values of a characteristic are equal, they can simply be added to the setup times related with equipping the machine for the subsequent job. Note that the removing time of the last job, then, is covered by the setup time for equipping of the first job. Note, furthermore, that due to symmetry the problem setting with setup times for equipping but without setup times for removing is equivalent to the problem setting with setup times for removing but without setup times for equipping.
-
Setup time differences We call the standard case value-dependent setup time. Here, equipping any value v for characteristic c may take individual setup times \(s^e_{v,c}\ge 0\). Analogously, individual setup times \(s^r_{v,c}\ge 0\) for removing v from c can occur. Furthermore, we distinguish the following special cases. We investigate the special case where setup times are only characteristic-dependent; that is, we have \(s^e_{v,c}=s^e_{c}\) and \(s^r_{v,c}=s^r_{c}\) for each characteristic \(c\in C\) and each value \(v\in V_c\). Furthermore, we analyze the special case where \(s^e_{c}=1\) and \(s^r_{c}=1\) for each characteristic \(c\in C\), so that all setup times are equal.
3 Analysis of computational complexity
3.1 Sequential setups
-
If there is a Hamiltonian path in \(G'\), then we can construct a schedule for \(I''\) by having the jobs in the same order as the corresponding nodes in the Hamiltonian path in \(G'\). We, then, have setup time of 2 prior to the first job. Furthermore, we have a setup time of 1 between each pair of consecutive jobs. This is true, because two jobs differ in exactly one characteristic’s value, if the corresponding nodes in \(G'\) are adjacent. Hence, there is a schedule for \(I''\) with makespan of at most \(2+(|V'|-1)=|V'|+1\).
-
Now, assume there is a schedule with a makespan of at most \(|V'|+1\). We have a setup time of 2 prior to the first job, which leaves \(|V'|-1\) total setup time for setups between pairs of consecutive jobs. Since there are no identical jobs, we have a setup time of at least 1 for each such pair. Hence, each pair of consecutive jobs corresponds to adjacent nodes in \(G'\), since non-adjacent nodes in \(G'\) incur a setup time of 2.
-
If j and \(j'\) are scheduled in the first two positions or in the last two positions, then total setup time for \(c_e\) is 2.
-
If j and \(j'\) are scheduled in consecutive positions p and \(p+1\), respectively, with \(p=2,\ldots ,n-2\) or in positions 1 and n, then total setup time for \(c_e\) is 3.
-
If j and \(j'\) are scheduled in non-consecutive positions p and \(p'\), respectively, with \(p=1\) and \(2<p'<n\) or \(1<p<n-1\) and \(p'=n\), then total setup time for \(c_e\) is 4.
-
If j and \(j'\) are scheduled in non-consecutive positions p and \(p'\), respectively, with \(1<p<p'-1<n'-1\), then total setup time for \(c_e\) is 5.
-
If there is a characteristic \(c_e\in C_{\sigma (1)}\cap C_{\sigma (n)}\), then the total setup time for characteristics in \(C_{\sigma (1)}\cup C_{\sigma (n)}\) is at leastObviously, the total setup time for \(c_e\) is 3. If and only if \(C_{\sigma (1)}\cap C_{\sigma (2)}\ne \emptyset \) (\(C_{\sigma (n-1)}\cap C_{\sigma (n)}\ne \emptyset \)), the total setup time for the characteristic in \(C_{\sigma (1)}\cap C_{\sigma (2)}\) (in \(C_{\sigma (n-1)}\cap C_{\sigma (n)}\)) is 2 leading to partial lower bound \(LB'_1\). The total setup time for at least one characteristic of \(\sigma (1)\) and at least one characteristic of \(\sigma (n)\) is 4 leading to the last term in \(LB_1\). Hence, total setup time for characteristics in \(C_{\sigma (1)}\cup C_{\sigma (n)}\) equals 15, if \(C_{\sigma (1)}\cap C_{\sigma (2)}\ne \emptyset \) and \(C_{\sigma (n-1)}\cap C_{\sigma (n)}\ne \emptyset \) and exceeds 15 otherwise.$$\begin{aligned}&LB_1=\underbrace{1\cdot 3}_{c_e}\nonumber \\&\quad +\underbrace{2\cdot 2}_{LB'_1}+2\cdot 4=15. \end{aligned}$$Among the \(1.5\cdot |V|-5\) other characteristics at most \(|V|-3\) can have total setup time of 3. In fact, if \(C_{\sigma (k)}\cap C_{\sigma (k+1)}\ne \emptyset \), \(k=2,\ldots ,n-2\), then total processing time of \(c_e\) with \(e=\{\sigma (k),\sigma (k+1)\}\) is 3. This leads to a total setup time for the \(1.5\cdot |V|-5\) remaining characteristics ofwith q being the number of pairs of consecutive jobs in \(\sigma (2),\ldots ,\sigma (n-1)\) having no characteristic in common. We, thus, obtain a lower bound of the total setup time for all characteristics of$$\begin{aligned} S_1(q)&=3\cdot (|V|-3-q)+5\cdot (0.5\cdot |V|-2+q)\nonumber \\&=5.5\cdot |V|-19+2\cdot q. \end{aligned}$$Furthermore, a total setup time of \(LB(0)=5.5\cdot |V|-4\) is achieved, if and only if \(C_{\sigma (k)}\cap C_{\sigma (k+1)}\ne \emptyset \) for each \(k=1,\ldots ,n-1\).$$\begin{aligned} LB(q)&=LB_1+S_1(q)=15+5.5\cdot |V|-19+2\cdot q\nonumber \\&=5.5\cdot |V|-4+2\cdot q. \end{aligned}$$
-
If \(C_{\sigma (1)}\cap C_{\sigma (n)}=\emptyset \), then the total setup time for characteristics in \(C_{\sigma (1)}\cup C_{\sigma (n)}\) is at leastPartial lower bound \(LB'_2\) is motivated as \(LB'_1\) above. The total setup time for the two remaining characteristics of \(\sigma (1)\) and \(\sigma (n)\), respectively, is 4 leading to the last term in \(LB_2\). Hence, the total setup time for the characteristics in \(C_{\sigma (1)}\cup C_{\sigma (n)}\) equals 20, if \(C_{\sigma (1)}\cap C_{\sigma (2)}\ne \emptyset \) and \(C_{\sigma (n-1)}\cap C_{\sigma (n)}\ne \emptyset \) and exceeds 20 otherwise.$$\begin{aligned} LB_2=\underbrace{2\cdot 2}_{LB'_2}+4\cdot 4=20. \end{aligned}$$For the \(1.5\cdot |V|-6\) remaining characteristics, we can derive a total setup time ofWe, thus, obtain a lower bound$$\begin{aligned} S_2(q)\!=\!3\cdot (|V|\!-\!3\!-\!q)\!+\!5\cdot (0.5\cdot |V|\!-\!3\!+\!q)\!=\!5.5\cdot |V|\!-\!24\!+\!2\cdot q. \end{aligned}$$Furthermore, a total setup time of \(LB(0)=5.5\cdot |V|-4\) is achieved, if and only if \(C_{\sigma (k)}\cap C_{\sigma (k+1)}\ne \emptyset \) for each \(k=1,\ldots ,n-1\).$$\begin{aligned} LB(q)\!=\!LB_2\!+\!S_2(q)\!=\!20\!+\!5.5\cdot |V|\!-\!24\!+\!2\cdot q\!=\!5.5\cdot |V|\!-\!4\!+\!2\cdot q. \end{aligned}$$
3.2 Parallel setups
-
In the original schedule, the setup time between s(j) and its immediate predecessor j and between \(j'\) and its immediate predecessor \(p(j')\) is \(2(s^r_{c_1}+s^e_{c_1})\). The last job in the schedule causes \(\max \left\{ s^r_{c}\mid c\in C\right\} \) setup time for removing.
-
In the new schedule, the setup time between s(j) and its immediate predecessor is at most \(s^r_{c_1}+s^e_{c_1}\) and the setup time between \(j'\) and its immediate predecessor j is at most \(s^r_{c_2}+s^e_{c_2}\le s^r_{c_1}+s^e_{c_1}\). Here, also, the last job in the schedule causes \(\max \left\{ s^r_{c}\mid c\in C\right\} \) setup time for removing.
\(v_{j,c}\) | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
\(c_1\) | 1 | 2 | 2 | 3 | 3 | 2 |
\(c_2\) | 4 | 6 | 5 | 5 | 6 | 6 |
\(c_3\) | 8 | 8 | 7 | 9 | 9 | 9 |
\(V_{c_1}\)
|
\(V_{c_2}\)
|
\(V_{c_3}\)
| |||||||
---|---|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
\(s^e_{v,c}\)
| 3 | 1 | 4 | ||||||
\(s^r_{v,c}\)
| 4 | 5 | 1 |
-
\(s^e_{p_1,c_1}=p_x\) and \(s^r_{p_1,c_1}=B-p_x\) for characteristic \(c_1\),
-
\(s^e_{p_2,c_2}=B-p_x\) and \(s^r_{p_2,c_2}=p_x\) for \(c_2\),
-
\(s^e_{p_3,c_3}=p_y\) and \(s^r_{p_3,c_3}=B-p_y\) for \(c_3\),
-
\(s^e_{p_4,c_4}=B-p_y\) and \(s^r_{p_4,c_4}=p_y\) for \(c_4\),
-
\(s^e_{p_5,c_5}=B\) and \(s^r_{p_5,c_5}=0\) for \(c_5\) and
-
\(s^e_{p_6,c_6}=0\) and \(s^r_{p_6,c_6}=B\) for \(c_6\).
-
\(s^e_{u_1,c_1}=0\), \(s^e_{v_1,c_1}=v_x\), \(s^r_{u_1,c_1}=B-u_x\), and \(s^r_{v_1,c_1}=0\) for \(c_1\),
-
\(s^e_{u_2,c_2}=0\), \(s^e_{v_2,c_2}=B-v_x\), \(s^r_{u_2,c_2}=u_x\), and \(s^r_{v_2,c_2}=0\) for \(c_2\),
-
\(s^e_{u_3,c_3}=0\), \(s^e_{v_3,c_3}=v_y\), \(s^r_{u_3,c_3}=B-u_y\), and \(s^r_{v_3,c_3}=0\) for \(c_3\),
-
\(s^e_{u_4,c_4}=0\), \(s^e_{v_4,c_4}=B-v_y\), \(s^r_{u_4,c_4}=u_y\), and \(s^r_{v_4,c_4}=0\) for \(c_4\),
-
\(s^e_{u_5,c_5}=0\), \(s^e_{v_5,c_5}=B\), \(s^r_{u_5,c_5}=0\), and \(s^r_{v_5,c_5}=0\) for \(c_5\) and
-
\(s^e_{u_6,c_6}=0\), \(s^e_{v_6,c_6}=0\), \(s^r_{u_6,c_6}=B\), and \(s^r_{v_6,c_6}=0\) for \(c_6\).
-
For each vertex \(i\in V\), we have a job i in \(I'\).
-
For each pair (j, k) of vertices with \(j<k\) of I, we introduce a characteristic \(c_{j,k}\) in \(I'\). In the following, we call these characteristics edge-characteristics.
-
The set of values for edge-characteristic \(c_{j,k}\) is \(V_{j,k}=\{j,k,0\}\).
-
For edge-characteristic \(c_{j,k}\), job j receives value \(v_{j,c_{j,k}}=j\), job k has value \(v_{k,c_{j,k}}=k\), and each other job i, \(i\ne j\) and \(i\ne k\), has value \(v_{i,c_{j,k}}=0\).
-
We set \(s^e_{j,c_{j,k}}=s^r_{j,c_{j,k}}=s^e_{k,c_{j,k}}=s^r_{k,c_{j,k}}=0\), that is equipping edge-characteristic \(c_{j,k}\) with j or k or removing j or k from \(c_{j,k}\) takes no time, if \(\{j,k\}\in E\). If \(\{j,k\}\not \in E\), we set \(s^e_{j,c_{j,k}}=s^r_{j,c_{j,k}}=s^e_{k,c_{j,k}}=s^r_{k,c_{j,k}}=1\). Finally, we set \(s^e_{0,c_{j,k}}=s^r_{0,c_{j,k}}=0\).
-
-
For each vertex \(i\in V\), we introduce a characteristic \(c_i\) in \(I'\). In the following, these characteristics are called vertex-characteristics.
-
The set of values for vertex-characteristics \(c_{i}\) is \(V_{i}=\{i,0\}\).
-
For vertex-characteristic \(c_i\), job i receives value \(v_{i,c_{i}}=i\), whereas each other job j, \(j\ne i\), has value \(v_{j,c_{i}}=0\).
-
We set \(s^e_{0,c_i}=s^r_{0,c_i}=0\), that is equipping vertex-characteristic \(c_{i}\) with value 0 or removing value 0 from \(c_{i}\) takes no time. Furthermore, we set \(s^e_{i,c_i}=s^r_{i,c_i}=1\).
-