## 3 The Optimality Box
### The Largest Relative Perimeter of the Optimality Box
The right scheduling decisions allow the plant to reduce the costs of productions due to better utilization of the machines. A shorter delivery time is archived with increasing customer satisfaction. In Sections 2-6, we used the notion of an optimality box of a job permutation \(\pi_{k}\) and proved useful properties of the optimality box \(\mathcal{OB}(\pi_{k},T)\). We investigated permutation \(\pi_{k}\) with the largest relative perimeter of the optimality box. Using these properties, we derived efficient algorithms for constructing the optimality box for a job permutation \(\pi_{k}\) with the largest relative perimeter of the box \(\mathcal{OB}(\pi_{k},T)\). From the computational experiments, it follows that the permutation \(\pi_{k}\) with the smallest values of the error function \(F(\pi_{k},t)\) for the optimality box \(\mathcal{OB}(\pi_{k},T)\) is close to the optimal permutation, which can be determined after completing the jobs when their processing times became known. In our computational experiments, we tested classes 1-7 of hard problems \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{Ul}|\sum C_{i}\), where the permutation constructed by Algorithm 3 outperforms the mid-point permutation, which is often used in the published algorithms applied to the problem \(1|p_{i}^{L}\leq p_{i}\leq p_{i}^{Ul}|\sum C_{i}\). The minimal, average and maximal errors \(\Delta\) of the objective function values were 0.045303%, 0.735154% and 4.773618%, respectively, for the permutations with smallest values of the error function \(F(\pi_{k},t)\) for the optimality boxes. The minimal, average and maximal errors \(\Delta_{mid-p}\) of the objective function values were 0.05378%, 0.936243% and 6.755918%, respectively, for the mid-point permutations. The minimal, average and maximal errors \(\Delta_{max}\) of the objective function values were 0.04705%, 0.82761% and 6.2441066%, respectively. Thus, Algorithm 3 solved all hard instances with a smaller error \(\Delta\) than other tested algorithms. The average relation \(\frac{\Delta_{mid-p}}{\Delta}\) for the obtained errors for all instances of classes 1-7 was equal to 1.33235. The average relation \(\frac{\Delta_{max}}{\Delta}\) for the obtained errors for all instances of classes 1-7 was equal to 1.1133116. Y.N. proved theoretical results; Y.N. and N.E. jointly conceived and designed the algorithms; N.E. performed the experiments; Y.N. and N.E. analyzed the data; Y.N. wrote the paper. The authors declare no conflict of interest. ## References

* (1) [PERSON]; [PERSON] A real-time production scheduler for a stochastic manufacturing environment. _Int. J. Prod. Res._**1988**, \(1\), 101-112. [CrossRef]
* (2) [PERSON] _Scheduling: Theory, Algorithms, and Systems;_ Prentice-Hall: Englewood Cliffs, NJ, USA, 2002. * (3) [PERSON]; [PERSON] Robust scheduling to hedge against processing time uncertainty in single stage production. _Manag. Sci._**1995**, _41_, 363-376. [CrossRef]
* (4) [PERSON]; [PERSON] Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research. _Int. J. Comput. Integr. Manuf._**2009**, _22_, 138-157. [CrossRef]
* (5) [PERSON]; [PERSON] _Sequencing and Scheduling with Inaccurate Data;_ Nova Science Publishers: Hauppauge, NY, USA, 2014. * (6) [PERSON] The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective. _Comput. Oper. Res._**2016**, _66_, 141-152. [CrossRef]
* (7) [PERSON]; [PERSON] Dispatching rules in scheduling: A fuzzy approach. _Int. J. Prod. Res._**1994**, _32_, 903-915. [CrossRef]
* (8) [PERSON]; [PERSON] Possibilistic minmax regret sequencing problems with fuzzy parameteres. _IEEE Trans. Fuzzy Syst._**2011**, _19_, 1072-1082. [CrossRef]
* (9) [PERSON]; [PERSON] Optimal fuzzy counterparts of scheduling rules. _Eur. J. Oper. Res._**1999**, _113_, 593-609. [CrossRef]* [PERSON] et al. (2002) [PERSON]; [PERSON]; [PERSON]; [PERSON] Stability of [PERSON]'s schedule with respect to limited machine availability. _Int. J. Prod.