Bazo do Nascimento 2020a - Revision history

Rimni: /* 5 Conclusions */

2021-12-14T14:54:42Z

‎5 Conclusions

Rimni at 12:31, 29 April 2021

2021-04-29T12:31:55Z

Rimni at 12:18, 29 April 2021

2021-04-29T12:18:44Z

Rimni: /* 4.1 Construction of the benchmarks */

2021-04-29T12:17:11Z

‎4.1 Construction of the benchmarks

Rimni at 12:16, 29 April 2021

2021-04-29T12:16:23Z

Show changes

Rimni: /* 4. Results and discussion */

2021-04-29T12:04:30Z

‎4. Results and discussion

Rimni: /* 4.1 Construction of the benchmarks */

2021-04-29T12:02:58Z

‎4.1 Construction of the benchmarks

Show changes

Rimni: /* 4. RESULTS AND DISCUSSION */

2021-04-29T11:35:57Z

‎4. RESULTS AND DISCUSSION

Rimni at 11:33, 29 April 2021

2021-04-29T11:33:52Z

Rimni: /* 3.2 Mathematical model */

2021-04-29T11:32:07Z

‎3.2 Mathematical model

@@ Line 782: / Line 782: @@
 Such complexity is expected due to the study of no-wait problems is, per se, hard. Even finding feasibility in models of this type is too computationally expensive.
-==5 Conclusions==
+==5. Conclusions==
 This work aims to present, to the best of our knowledge, a novel Open Shop Scheduling problem since it simultaneously addresses no-wait and resource constraints, something considerably difficult when such subjects are considered individually.

@@ Line 799: / Line 799: @@
 ==Referências==
-[1] Leung J.Y-T.(Ed.) Handbook of scheduling: Algorithms, models and performance analysis. Chapman and Hall/CRC, Boca Raton, 2004.
+[1] Leung J.Y-T.(Ed.) Handbook of scheduling: algorithms, models and performance analysis. Chapman and Hall/CRC, Boca Raton, 2004.
-[2] Pinedo M. Scheduling: Theory, Algorithms and Systems. Springer, New York, 2012.
+[2] Pinedo M. Scheduling: theory, algorithms and systems. Springer, New York, 2012.
-[3] Johnson, S.M. Optimal two- and three-stage production schedules with setup times included. Nav. Res. Log. Quarterly, 1:61-68, 1954.
+[3] Johnson S.M. Optimal two- and three-stage production schedules with setup times included. Nav. Res. Log. Quarterly, 1:61-68, 1954.
-[4] Gonzalez T., Sahni, S. Open Shop Scheduling to Minimize Finish Time. J. of the ACM, 23:665-679, 1976.
+[4] Gonzalez T., Sahni, S. Open shop scheduling to minimize finish time. J. of the ACM, 23:665-679, 1976.
-[5] Liu C.B.R. Scheduling ordered open shops. Comp. Oper. Res, 14:257-264, 1987.
+[5] Liu C.B.R. Scheduling ordered open shops. Comp. Oper. Res., 14:257-264, 1987.
 [6] Prins C. An overview of scheduling problems arising in satellite communications. J. Oper. Res. Soc., 40:611-623, 1994.
@@ Line 814: / Line 815: @@
 [7] Matta M. A genetic algorithm for the proportionate multiprocessor open shop. Comp. Oper. Res., 36:2601-2618, 2009.
-[8] Ciro G.C., Dugardin F., Yalaoui F., Kelly R. Open shop scheduling with a multi-skills resource constraint: a genetic algorithm and an ant colony optimization approach. Int. J. Oper. Res., 1-29, 2015.
+[8] Ciro G.C., Dugardin F., Yalaoui F., Kelly R. Open shop scheduling with a multi-skills resource constraint: a genetic algorithm and an ant colony optimization approach. Int. J. Oper. Res., 54(167):4854-4881, 2016.
-[9] Chen B., Potts C.N., Woeginger, G.J. A review of machine scheduling: Complexity, Algorithms and Applications. In Du D.Z., Pardalos, P.M. (Eds.). Handbook of Combinatorial Optimization, 21-169, 1998.
+[9] Chen B., Potts C.N., Woeginger, G.J. A review of machine scheduling: complexity, algorithms and applications. In Du D.Z., Pardalos, P.M. (Eds.), Handbook of Combinatorial Optimization, 21-169, 1998.
-[10] Sahni S., Cho Y. Complexity of Scheduling Shops with No Wait in Process. Math. Oper. Res., 4:448-457, 1979.
+[10] Sahni S., Cho Y. Complexity of scheduling shops with no wait in process. Math. Oper. Res., 4(4):303-477, 1979.
-[11] Hall N.G., Sriskandarajah C. A Survey of Machine Scheduling Problems with Blocking and No-wait in Process. Oper. Res., 44:510-525, 1996.
+[11] Hall N.G., Sriskandarajah C. A survey of machine scheduling problems with blocking and no-wait in process. Oper. Res., 44:510-525, 1996.
 [12] Allahverdi A. A survey of scheduling with no-wait in process. Eur. J. Oper. Res., 255:665-686, 2016.
@@ Line 826: / Line 827: @@
 [13] Naderi B., Zandieh M. Modeling and scheduling no-wait open shop problems. Int. J. Prod. Econ., 158:256-266, 2014.
-[14] Blazewicz J., Lenstra J.K.,  Rinnooy Kan, A.H.G. Scheduling subject to resource constraints: classification and complexity. Discr. App. Math., 5:11-24, 1983.
+[14] Blazewicz J., Lenstra J.K.,  Rinnooy Kan A.H.G. Scheduling subject to resource constraints: classification and complexity. Discr. App. Math., 5(1):11-24, 1983.
-[15] Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discr. Math, 1979.
+[15] Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discr. Math, 5:287-326, 1979.
-[16] Oulamara A., Rebaine D., Serairi M. Scheduling the two-machine open shop problem under resource constraints for setting the jobs. Ann. Oper. Res. 211:333-356, 2013.
+[16] Oulamara A., Rebaine D., Serairi M. Scheduling the two-machine open shop problem under resource constraints for setting the jobs. Ann. Oper. Res., 211:333-356, 2013.
-[17] Borissova D. An Optimal Staffing and Scheduling Approach in Open Shop Environment. Comptes Rendus de L’Académie bulgare des Sciences, 60:1295-1300, 2015.
+[17] Borissova D. An optimal staffing and scheduling approach in open shop environment. Comptes Rendus de L’Académie bulgare des Sciences, 60:1295-1300, 2015.
-[18] Ciro G.C., Dugardin F., Yalaoui F., Kelly R. A fuzzy ant colony optimization to solve an open shop scheduling problem with multi-skills resource constraint, IFAC – Papers Online, 48:715-720, 2015.
+[18] Ciro G.C., Dugardin F., Yalaoui F., Kelly R. A fuzzy ant colony optimization to solve an open shop scheduling problem with multi-skills resource constraint. IFAC – Papers Online, 48:715-720, 2015.
 [19] Ciro G.C., Dugardin F., Yalaoui F., Kelly R. A NSGA-II and NSGA-III comparison for solving an open shop scheduling problem with resource constraint. IFAC – Papers Online, 49:1272-1277, 2016.

@@ Line 782: / Line 782: @@
 Such complexity is expected due to the study of no-wait problems is, per se, hard. Even finding feasibility in models of this type is too computationally expensive.
-=5 CONCLUSIONS=
+==5 Conclusions==
-''' '''This work aims to present, to the best of our knowledge, a novel Open Shop Scheduling problem since it simultaneously addresses no-wait and resource constraints, something considerably difficult when such subjects are considered individually.
+This work aims to present, to the best of our knowledge, a novel Open Shop Scheduling problem since it simultaneously addresses no-wait and resource constraints, something considerably difficult when such subjects are considered individually.
 This originality is obtained from the addition of no-wait constraints and the variable <math display="inline">K</math> related to the start time of the jobs – the main result to be garnered when it comes to the continuous and uninterrupted production of a job –, to the Open Shop model of [8], making the necessary adaptations.
@@ Line 798: / Line 798: @@
 We would like to thank CAPES for funding the research.
-==REFERÊNCIAS ==
+==Referências==
-[1] Leung, J.Y-T.(Ed.) Handbook of Scheduling: Algorithms, Models and Performance Analysis. Chapman and Hall/CRC, Boca Raton, 2004.
+[1] Leung J.Y-T.(Ed.) Handbook of scheduling: Algorithms, models and performance analysis. Chapman and Hall/CRC, Boca Raton, 2004.
 [2] Pinedo M. Scheduling: Theory, Algorithms and Systems. Springer, New York, 2012.

@@ Line 364: / Line 364: @@
 {| style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: auto;max-width: auto;"
 |-
-|style="padding:10px;"| [[Image:Draft_Bazo do Nascimento_138238743-image1.jpeg|426px]]
+|style="padding:10px;"| [[Image:Draft_Bazo do Nascimento_138238743-image1.jpeg|526px]]
 |- style="text-align: center; font-size: 75%;"
 | colspan="1" style="padding:10px;"| '''Figure 1'''. Pseudocode of the benchmark generator

@@ Line 397: / Line 397: @@
 <div id='tab-1'></div>
-{| class="wikitable" style="margin: 1em auto 0.1em auto;border-collapse: collapse;font-size:85%;width:auto;"
+{| class="wikitable" style="margin: 1em auto 0.1em auto;border-collapse: collapse;font-size:85%;width:30%;"
 |-style="text-align:center"
 ! J !!  VIG !! OS !! SOS !! <math display="inline">\overline{SOS}</math> % !! INC !! INF

@@ Line 353: / Line 353: @@
 In brief, the set (7)-(8) was proposed in this paper and incorporated into the original model. Besides, the variable <math display="inline">{K}_{i}</math> referring to the time when the job starts to be processed, was added in Constraint (3), which establishes that start time will always be positive. Ultimately, the Constraint (17) was adapted, adding the variable as mentioned earlier to it.
-==4. RESULTS AND DISCUSSION==
+==4. Results and discussion==
 ''' '''This chapter is divided into two parts—the first being dedicated to how the instances used in the mathematical model validation are built. The second is related to the presentation of the results of the work and its potential aftermath.
-===4.1 Construction of the Benchmarks===
+===4.1 Construction of the benchmarks===
-Each benchmark used was built randomly, from the combination of four parameters, namely, the number of jobs, machines, workers, and skills. For the first three, the values vary between 3 and 10, while for the last, the values range between 3 and 7. Furthermore, the values for the number of workers and the number of machines must be the same since we assume a resource (worker) per machine. Thus, for each level, represented by the number of jobs to be sequenced, there is a total of 40 benchmarks. As the number of tiers is equal to 8, it is possible to construct 320 examples for the problem studied. A formal description of the process is presented in Fig. 1.
+Each benchmark used was built randomly, from the combination of four parameters, namely, the number of jobs, machines, workers, and skills. For the first three, the values vary between 3 and 10, while for the last, the values range between 3 and 7. Furthermore, the values for the number of workers and the number of machines must be the same since we assume a resource (worker) per machine. Thus, for each level, represented by the number of jobs to be sequenced, there is a total of 40 benchmarks. As the number of tiers is equal to 8, it is possible to construct 320 examples for the problem studied. A formal description of the process is presented in [[#img-1|Figure 1]].
-[[Image:Draft_Bazo do Nascimento_138238743-image1.jpeg|426px]]
+<div id='img-1'></div>
 However, in just one generation, we found that many sets were not obtained. Thus, for each generation, 100 replications were performed, making it possible to obtain 320,000 benchmarks. For the tests carried out, we decided to use only one example of the acquired set, according to the oldest generation. Due to this seniority criterion, the first generation of the parameter set is considered, discarding the others.

@@ Line 261: / Line 261: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" |<math>{Z}_{im{m}^{'}}+{Z}_{i{m}^{'}m}=1 \quad\forall i\in J;\forall m,{m}^{'}\in L; \quad m\not ={m}^{'}</math>
+| style="text-align: center;" |<math>{Z}_{im{m}^{'}}+{Z}_{i{m}^{'}m}=1 \quad\forall i\in J; \quad \forall m,{m}^{'}\in L; \quad m\not ={m}^{'}</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(10)
@@ Line 281: / Line 281: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" |<math>{V}_{imj{m}^{'}}+{V}_{j{m}^{'}im}\geq {Y}_{wim}+{Y}_{wj{m}^{'}}-1\quad \forall i,j\in J;i\not =j; \quad \forall m,{m}^{'}\in L;\forall w\in W</math>
+| style="text-align: center;" |<math>{V}_{imj{m}^{'}}+{V}_{j{m}^{'}im}\geq {Y}_{wim}+{Y}_{wj{m}^{'}}-1\quad \forall i,j\in J;i\not =j; \quad \forall m,{m}^{'}\in L; \quad \forall w\in W</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(12)

@@ Line 221: / Line 221: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" |<math>{C}_{wim}-G\left( 1-{V}_{imj{m}^{'}}\right) \leq {C}_{wj{m}^{'}}-{SE}_{j{m}^{'}}-</math><math>{p}_{j{m}^{'}} \forall i,j\in J;\forall m,{m}^{'}\in L;\forall w\in W</math>
+| style="text-align: center;" |<math>{C}_{wim}-G\left( 1-{V}_{imj{m}^{'}}\right) \leq {C}_{wj{m}^{'}}-{SE}_{j{m}^{'}}-</math><math>{p}_{j{m}^{'}} \quad \forall i,j\in J;\quad \forall m,{m}^{'}\in L;\forall w\in W</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(6)
@@ Line 231: / Line 231: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" |<math>{C}_{wim}\geq {K}_{i}+{p}_{im} \forall i\in J;\forall m\in L;\forall w\in W</math>
+| style="text-align: center;" |<math>{C}_{wim}\geq {K}_{i}+{p}_{im} \quad \forall i\in J; \quad\forall m\in L;\forall w\in W</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(7)
@@ Line 241: / Line 241: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" | <math>{C}_{wim}\leq {K}_{i}+\sum _{m=1}^{M}{p}_{im}</math>
+| style="text-align: center;" | <math>{C}_{wim}\leq {K}_{i}+\sum _{m=1}^{M}{p}_{im}\quad\forall i\in J;\quad\forall w\in W</math>
-<math>\forall i\in J;\forall w\in W</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(8)
@@ Line 252: / Line 251: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" |<math>{X}_{ijm}+{X}_{jim}=1</math><math>\forall i,j\in J;i\not =j;\forall m\in L</math>
+| style="text-align: center;" |<math>{X}_{ijm}+{X}_{jim}=1 \quad\forall i,j\in J; \quad i\not =j;\forall m\in L</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(9)
@@ Line 262: / Line 261: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" |<math>{Z}_{im{m}^{'}}+{Z}_{i{m}^{'}m}=1</math>
+| style="text-align: center;" |<math>{Z}_{im{m}^{'}}+{Z}_{i{m}^{'}m}=1 \quad\forall i\in J;\forall m,{m}^{'}\in L; \quad m\not ={m}^{'}</math>
-<math>\forall i\in J;\forall m,{m}^{'}\in L;m\not ={m}^{'}</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(10)
@@ Line 273: / Line 271: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" |<math>{V}_{imj{m}^{'}}+{V}_{j{m}^{'}im}\leq 1</math><math>\forall i,j\in J;\forall m,{m}^{'}\in L</math>
+| style="text-align: center;" |<math>{V}_{imj{m}^{'}}+{V}_{j{m}^{'}im}\leq 1\quad \forall i,j\in J; \quad\forall m,{m}^{'}\in L</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(11)
@@ Line 283: / Line 281: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" |<math>{V}_{imj{m}^{'}}+{V}_{j{m}^{'}im}\geq {Y}_{wim}+{Y}_{wj{m}^{'}}-1</math><math>\forall i,j\in J;i\not =j;\forall m,{m}^{'}\in L;\forall w\in W</math>
+| style="text-align: center;" |<math>{V}_{imj{m}^{'}}+{V}_{j{m}^{'}im}\geq {Y}_{wim}+{Y}_{wj{m}^{'}}-1\quad \forall i,j\in J;i\not =j; \quad \forall m,{m}^{'}\in L;\forall w\in W</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(12)
@@ Line 293: / Line 291: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" | <math>{V}_{imi{m}^{'}}+{V}_{i{m}^{'}im}\geq {Y}_{wim}+{Y}_{wi{m}^{'}}-1</math><math>\forall i\in J;\forall m,{m}^{'}\in L;m\not ={m}^{'};\forall w\in W</math>
+| style="text-align: center;" | <math>{V}_{imi{m}^{'}}+{V}_{i{m}^{'}im}\geq {Y}_{wim}+{Y}_{wi{m}^{'}}-1 \quad \forall i\in J; \quad \forall m,{m}^{'}\in L; \quad m\not ={m}^{'}; \quad \forall w\in W</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(13)
@@ Line 303: / Line 301: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" | <math>{Y}_{wim}\leq {RE}_{ims}\times {A}_{ws}+(1-{RE}_{ims})</math>
+| style="text-align: center;" | <math>{Y}_{wim}\leq {RE}_{ims}\times {A}_{ws}+(1-{RE}_{ims})\quad \forall i\in J; \quad \forall m\in L;\quad \forall w\in W;\quad \forall s\in S</math>
-<math>\forall i\in J;\forall m\in L;\forall w\in W;\forall s\in S</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(14)
@@ Line 314: / Line 311: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" |<math>\sum _{i=1}^{N}\sum _{m=1}^{M}{Y}_{wim}\geq 1</math><math>\forall w\in W</math>
+| style="text-align: center;" |<math>\sum _{i=1}^{N}\sum _{m=1}^{M}{Y}_{wim}\geq 1</math><math>\quad \forall w\in W</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(15)
@@ Line 324: / Line 321: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" |<math>\sum _{w=1}^{W}{Y}_{wim}=1</math><math>\forall i\in J;\forall m\in L</math>
+| style="text-align: center;" |<math>\sum _{w=1}^{W}{Y}_{wim}=1\quad \forall i\in J; \quad\forall m\in L</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(16)
@@ Line 334: / Line 331: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" | <math>{C}_{wim}-{K}_{i}-{SE}_{im}-{p}_{im}\geq {r}_{i}</math><math>\forall i\in J;\forall m\in L;\forall w\in W</math>
+| style="text-align: center;" | <math>{C}_{wim}-{K}_{i}-{SE}_{im}-{p}_{im}\geq {r}_{i}\quad \forall i\in J;\quad \forall m\in L;\quad \forall w\in W</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(17)
@@ Line 344: / Line 341: @@
 {| style="text-align: center; margin:auto;width: 100%;"
 |-
-| style="text-align: center;" |<math>{X}_{ijm},{Z}_{im{m}^{'}},{Y}_{wim},{V}_{imj{m}^{'}}\in \lbrace 0,1\rbrace</math><math>\forall i,j\in J;\forall m,{m}^{'}\in L;\forall w\in W</math>
+| style="text-align: center;" |<math>{X}_{ijm},{Z}_{im{m}^{'}},{Y}_{wim},{V}_{imj{m}^{'}}\in \lbrace 0,1\rbrace\quad \forall i,j\in J; \quad \forall m,{m}^{'}\in L; \quad\forall w\in W</math>
 |}
 |  style="text-align: center;width: 5px;text-align: right;white-space: nowrap;"|(18)