Complexity of J3|pij=1|Cmax

[m-renken]

Currently, J3|pij=1|Cmax is listed as strongly NP-hard with a reference to Lenstra and Rinnooy Kan (https://doi.org/10.1016/S0167-5060(08)70821-5). However, the hardness shown in that paper is actually for the problem variant with recirculation, whereas the problem definition given in the scheduling zoo excludes recirculation by default. I do not know whether the computational complexity of J3|pij=1|Cmax (without recirculation) has been settled.

[xtof-durr]

Dear M. Renken,

I looked at this paper. The proof starts in page 16, but I don't see explicitly the word recirculation. Sorry I cannot help much, since I don't know enough about Job-scheduling. So I cannot say, if we cited the wrong paper for this result, or if we cited the wrong result. Maybe Sigrid you know better?

Sincerely yours,

Christoph Dürr

Le 11/05/2023 à 17:17, m-renken a écrit :

Currently, |J3|pij=1|Cmax| is listed as strongly NP-hard with a reference to Lenstra and Rinnooy Kan (https://doi.org/10.1016/S0167-5060(08)70821-5). However, the hardness shown in that paper is actually for the problem variant /with recirculation/, whereas the problem definition given in the scheduling zoo excludes recirculation by default. I do not know whether the computational complexity of |J3|pij=1|Cmax| (without recirculation) has been settled.

— Reply to this email directly, view it on GitHub https://github.com/xtof-durr/schedulingzoo/issues/4, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAMV5GA2XNNNX2IKGD3GPSDXFT7HZANCNFSM6AAAAAAX6JAU6I. You are receiving this because you are subscribed to this thread.Message ID: @.***>

[m-renken]

You will not find the word "recirculation", but you can see in the definition of "3-MACHINE UNIT-TIME JOB SHOP" that they only forbid \mu_{j,h} = \mu_{j,h-1} but allow e.g. \mu_{j,h} = \mu_{j,h-2}.

[xtof-durr]

Very good, I changed that complexity result in the bibtex files. Next time I promize to be quicker in correcting things !