- A critical note on [A. Janiak, M. Y. Kovalyov, M. Lichtenstein. Strong NP-hardness of scheduling problems with learning or aging effect. Annals of Operations Research, 206:577-583, 2013]
I am against arguing about idle findings, therefore, I thought it would be possible to avoid hereby discussion concerning artificially new, but first and foremost incorrect, results presented by Janiak et al. [A. Janiak, M. Y. Kovalyov, M. Lichtenstein, Strong NP-hardness of scheduling problems with learning or aging effect. Annals of Operations Research, 206:577-583, 2013]. However, these incorrect results are being used by these authors as arguments against my work, thereby I am obligated to refer to them.
Namely, Janiak et al. [6] were trying to show that the strong NP-hardness proofs in my papers ([1], [2], [3]) contained errors, which required their corrections ([6]). Moreover, they claimed that our proofs in [4] and [5] had such errors that (even) they were unable to correct them, thereby the computational complexity of the related problems is still open issue.
Nevertheless, in the enclosed paper, we will show that the so called “corrections” presented by Janiak et al. are exaggerated, since they concerns only some informal simplifications in our proofs. The “formalization” of these proofs will be shown here, which requires only few comments that are the same for all the proofs. It also shows the strength of our approach that supports the strong NP-hardness proving process. Moreover, we will also prove that the claims of Janiak et al. that computational complexity of the problems analysed in [4] and [5] “remains unknown because of another mistake”, which they are unable to correct, follows from their own mistake with adding parameters.
Some simplifications in our proofs were exaggerated by Janiak et al. to the so called “mistake”. Since in face of such few words that can confuse, more words can be required to show the facts, therefore, we feel that readers deserve more detailed explanation, which is given below. It is in some way redundant to our previous elucidation, but here we additionally refer to “results” given by Janiak et al.The critical note can be found here:
A critical note on “Strong NP-hardness of scheduling problems with learning or aging effect by A. Janiak, M. Y. Kovalyov, M. Lichtenstein”[Important]:
It has been revealed in forumakademickie.pl and in the review that A. Janiak has contacted the Editor of Annals of Operations Research (his former co-author and colleague) and he has requested him to choose reviewers for his own paper (Janiak et al.) among names pointed by A. Janiak (his colleagues). Moreover, A .Janiak has contacted the chosen reviewers and pressing them for positive reviews of his paper.
Usually – a fair habit – is to invited the author of an original paper as one of the reviewers for a submission about only his work (as in this case), but the Editor of Annals of Operations Research omitted me in this process. Later on, the Editor of Annals of Operations Research has been blocking all my scientific discussion concerning the false and misleading publication of Janiak et al. and preventing publication of my mathematically justified counter-arguments.This is the explanation, how Janiak et al. were able to publish a paper, which contains false claims and mathematical mistakes.
References
[1] R. Rudek. Computational complexity and solution algorithms for flowshop scheduling problems with the learning effect. Computers & Industrial Engineering, 61:20-31, 2011.
[2] R. Rudek. On single processor scheduling problems with learning dependent on the number of processed jobs. Applied Mathematical Modelling, 37:1523-1536, 2013.
[3] R. Rudek. Scheduling problems with position dependent job processing times: computational complexity results. Annals of Operations Research, 196:491-516, 2012.
[4] R. Rudek. Some single-machine scheduling problems with the extended sum-of-processing-time based aging effect. International Journal of Advanced Manufacturing Technology, 59:299-309, 2012.
[5] R. Rudek. The strong NP-hardness of the maximum lateness minimization scheduling problem with the processing-time based aging effect. Applied Mathematics and Computation, 218:6498-6510, 2012.
[6] A. Janiak, M. Y. Kovalyov, M. Lichtenstein. Strong NP-hardness of scheduling problems with learning or aging effect. Annals of Operations Research, 206:577-583, 2013.
- A critical note on [A. Janiak, M. Y. Kovalyov, M. Lichtenstein. On a single machine-scheduling problem with separated position and resource effects, Optimization, 2013, DOI:10.1080/02331934.2013.804077]
This critical note refers to another part of a sequel of fake results recently published by Janiak et al. These authors are trying to find “mistakes” in our correct papers. The source of their faulty claims is the selective and incorrect analysis applied by Janiak et al.
Namely, it concerns the paper [A. Janiak, M. Y. Kovalyov, M. Lichtenstein. On a single machine-scheduling problem with separated position and resource effects. Optimization, 2013, DOI:10.1080/02331934.2013.804077], where Janiak et al. provided selective and incorrect analysis of our clear and obvious proof of an optimality for a resource allocation algorithm. In the meaning of these authors [2], their analysis should show incorrectness of our proof [1]. Furthermore, to make their claims stronger, they also provided a counter-example, which allegedly should prove the incorrectness of our resource allocation algorithm. Next, they presented the pseudocode, which in their meaning referred to a correct method.
Nevertheless, we show that in fact, Janiak et al. [2] omitted in their analysis significant and integral part of our proof, which is the source of their misleading and incorrect claims. Moreover, they analysed an algorithm that has nothing in common with the method presented in our paper [1], whereas our algorithm provides the correct result for their counter-example. Finally, the method published by Janiak et al. is exactly the pseudocode of the algorithm already described in our discussed paper, but they did not even mention about it.The critical note can be found here:
A critical note on “On a single machine-scheduling problem with separated position and resource effects by A. Janiak, M. Y. Kovalyov, M. Lichtenstein”and it was published (in the same journal as Janiak et al.):
R. Rudek, A. Rudek, A note “On a single machine-scheduling problem with separated position and resource effects”, Optimization – A Journal of Mathematical Programming and Operations Research, 64:2043-2046, 2015.
References
[1] A. Rudek, R. Rudek. A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models. Computers & Mathematics with Applications, 62:1870-1878, 2011.
[2] A. Janiak, M. Y. Kovalyov, M. Lichtenstein. On a single machine-scheduling problem with separated position and resource effects. Optimization, 2013, DOI:10.1080/02331934.2013.804077.
- Elucidation of the idea of some strong NP-hardness proofs
We present an elucidation of the idea of the strong NP-hardness proofs of some scheduling problems with variable job processing times presented in our papers. The reason is that A. Janiak, M. Y. Kovalyov, M. Lichtenstein try to mistakenly show that there are some errors. They even forced reviewers (their colleagues) and the Editor (their coauthor of other papers) to publish their fake results. However, our papers are correct, which is clearly showed below. Namely, in the original papers, we provided the relevant fundamental calculations and additionally also brief descriptions of the ideas of the proofs. We assumed that more detailed descriptions were redundant for the considered strong NP-hardness proofs, since the calculations were given. However, we have been informed that few readers focused only on the descriptions of the ideas omitting the calculations. Thus, the proofs may be prerceived to be informal as a sketch. Therefore, the objective of this note is to clearly point out the relation between the ideas and the calculations. We also describe the full idea showing the formal explanation.
Although there are no new results (nor any corrections, but comments) in this note, we hope it will help to understand our proofs of the strong NP-hardness (and first of all how the transformations were obtained), if some calculation details are confusing or overlooked during reading the original papers.
The elucidation can be found here:
Elucidation of the idea of some strong NP-hardness proofsWe have been pointed out that the above elucidation may be too large. Therefore, we present its minimized version that can be found here:
Elucidation of the idea of some strong NP-hardness proofs (minimized version)See also the elucidation in the description of the proof to Theorem 2 (part “If”) in:
A. Rudek, R. Rudek, Makespan minimization flowshop with position dependent job processing times – computational complexity and solution algorithms, Computers & Operations Research, 40:2071-2082, 2013.
and here (Theorem 1 part “If” and Section 3.3):
R. Rudek, The computational complexity analysis of the two-processor flowshop problems with position dependent job processing times, Applied Mathematics and Computation, 221:819-832, 2013.
In case of any questions, please do not hesitate to contact me.
- Statement concerning my short note: R. Rudek, A note on proving the strong NP-hardness of a scheduling problem with position dependent job processing times, Optimization Letters, 2012, doi: 10.1007/s11590-012-0445-0 (in press) [accepted: 2012-01-12; published on-line: 2012-01-28].
This statement concerns my short note [3] that is based on the paper [1] published by prof. Adam Janiak and dr Aleksander Bachman in 2004 in the Journal of the Operational Research Society. My note revealed a mistake that can be made during proving the strong NP-hardness. My intention was not to undermine the results presented by dr Bachman and prof. Janiak, which anyway have the very high quality, and such observations as mine would not affect it.
The note was intended to be a useful hint for other researchers how to avoid mistakes during proving strong NP-hardness. Nevertheless, I am afraid that the interpretation by prof. Adam Janiak was quite different. There are many untrue and unfair statements by prof. Janiak concerning my note [3] and published in different places. Therefore, I would like to make the following statement concerning my short note.On 2011-01-22, I have submitted to Journal of the Operational Society (JORS) my short note (viewpoint) [2] concerning the strong NP-hardness proof by dr Bachman and prof. Janiak [1], where I have showed that dr Bachman and prof. Janiak made a mistake and they did not prove the strong NP-hardness, but NP-hardness only.
On 2011-04-19, I have received a review (“We would like to publish your Viewpoint in JORS, but at present the format of the manuscript is not suitable“) that my viewpoint required minor changes (reduction of the manuscript). I have resubmitted it on 2011-04-22. However, after about 4 months (on 2011-08-18) I was informed that my note is rejected due to the response to my viewpoint by prof. Janiak. I was confused since no other explanation was given (except the sentence “a revised proof of the result“). I have no idea what is the revised proof made by prof. Janiak on a reviewer level that caused rejection of my viewpoint [2]. Thus, I thought that the only revision that can be done on this level concerned the term “strong NP-hardness” in [1] was replaced with “NP-hardness“. It seemed to be a reasonable excuse for the authors, since in such case there was no error in [1], but only typos.
Nevertheless, assuming that it was a mistake in the proof, then showing it seemed not trivial nor obvious (taking into consideration that it has not been noticed since 2004, and [2] was cited over 60 times). Therefore, I have decided to published my note in another journal. I have informed prof. Janiak and JORS about my decision, but I have received no answer nor any explanations what the corrections were made by prof. Janiak (on a level of a reviewer).
On 2011-09-13 I submitted my note to Optimization Letters and on 2012-01-12 it was accepted for publication and published on-line on 2012-01-28.
However, some time ago after my note [3] was published on-line, I was acquainted with the whole situation. It is worth highlighting that, while prof. Janiak was still acting as the only reviewer of my viewpoint [2] (when it was submitted to JORS), he sent it to prof. Mikhail Y. Kovalyov (which is against Ethics Policy). Next, in the same time prof. Janiak used my results [2] to submit his own new paper [4] (with completely new proof of the strong NP-hardness that was based on my observations) with completely another (not dr Bachman) author (i.e., with prof. Kovalyov). I have never expected that a reviewer could behave in such a way, i.e., to submit with another person their own new article [4] that is based on the paper (viewpoint) [2] still being under review.
In normal circumstances reviewer checks the paper (viewpoint), and if the observations are correct, then the viewpoint is accepted for publication (as it is usual for finding mistakes in other papers). After publication of such a viewpoint, the answer (i.e., by the authors of the original paper, or by other readers) can be submitted to the journal with the new correct results. In this case, prof. Janiak (being a reviewer) behaved as an author and used results that were presented to him for review only to submit his own new paper (instead of waiting for official publication of my results).
It is worth noticing that the paper by prof. Janiak and prof. Kovalyov [4] was accepted on 2012-01-16 (whereas mine was accepted on 2012-01-12) and published on-line on 2012-04-25 (mine was published on-line on 2012-01-28).
Since I did not know about the new proof by prof. Janiak and prof. Kovalyov when my note [3] was published, there is the following sentence “the complete computational complexity of this problem is still an open issue: strongly or ordinary NP-hard?“. If I knew about the new paper by prof. Janiak and prof. Kovalyov, then I would simply remove this sentence. Additionally, I would add a proper reference to the new proof made by prof. Janiak and prof. Kovalyov if available, which I have done in [5].
Therefore, I am very pity that my note, which was intended to be a useful hint for other researchers how to avoid mistakes during proving strong NP-hardness, turned out to be something completely different for prof. Janiak.References
[1] A. Bachman, A. Janiak, Scheduling jobs with position dependent processing times. Journal of the Operational Research Society 55:257-264, 2004.
[2] R. Rudek, Viewpoint on: Scheduling jobs with position-dependent processing times (Journal of the Operational Research Society 55 (2004) 257-264) submitted to Journal of the Operational Research Society on 2011-01-22.
[3] R. Rudek, A note on proving the strong NP-hardness of a scheduling problem with position dependent job processing times. Optimization Letters 7:613-616, 2013 [accepted: 2012-01-12; published on-line: 2012-01-28].
[4] A. Janiak, M. Y. Kovalyov, Corrigendum to: Scheduling jobs with position-dependent processing times. Journal of the Operational Research Society 63:1018-1020, 2012 [accepted: 2012-01-16; published on-line: 2012-04-25].
[5] M. Cross, Corrigendum to “On single processor scheduling problems with learning dependent on the number of processed jobs” [Appl. Math. Modell. 37 (3) (2013) 1523–1536]. Applied Mathematical Modelling 37:7888, 2013.