Jacek Błażewicz - Selected Publications#

J. Blazewicz, J.K. Lenstra, A.H.G. Rinnooy Kan, Scheduling subject to resource constraints: classification and complexity, Discrete Applied Mathematics 5, 1983, pp. 11-24 (1938 cit.-GS, 864 cit.-WoS). This seminal paper defined a new direction in machine scheduling theory by adding additional resources to the classical machine scheduling model. This work removed one of the key bottlenecks of scheduling theory. The paper continues to be one of the 10 most accessed and cited papers of Discrete Applied Mathematics.

J. Blazewicz, M. Drabowski, J. Węglarz, Scheduling multiprocessor tasks to minimize schedule length, IEEE Trans. on Computers 35, 1986, pp. 389-393 (364 cit.-GS, 164 cit.-WoS). In this paper, prof. Blazewicz introduced a new model involving multiprocessor task scheduling (motivated by a real-life example arising in parallel computer systems and used in the testing of electronic devices). This work underpinned a new research direction associated with parallel processors. It was also selected as one of the 10 most important papers in the area of scheduling as published in the volume edited by Stankovic and Ramamritham (J.A. Stankovic, K. Ramamritham, “Tutorial: Hard Real-Time Systems”, IEEE Computer Society Press, Washington, 1988).

J. Blazewicz, Minimizing mean weighted information loss with preemptible tasks and parallel processors, Technology and Science of Informatics 3, 1984, pp. 415-420 (100 cit.-GS, 72 cit.-WoS). This paper introduced the new criterion – “mean weighted information loss” or “weighted error for imprecise computations”. This finding sparked new research by several international teams. In the handbook edited by J. Leung (“Handbook of Scheduling. Algorithms, Models and Performance Analysis”, Chapman & Hall / CRS, Boca Raton, 2004), several authors stressed the pioneering role of this paper. Recently with the development of the new techniques used by drons, this topic got a new attention which in turn resulted in several citations of this paper.

J. Blazewicz, K. Ecker, G. Schmidt, J. Weglarz, Scheduling in Computer and Manufacturing Systems, Springer Verlag, Berlin, New York, 1993; 2nd Ed.1994, Electronic Edition 2012; J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, J. Weglarz, Scheduling Computer and Manufacturing Processes, Springer Verlag, Berlin, New York, 1996; 2nd Ed.2001; J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, J. Weglarz, Handbook on Scheduling: from Theory to Applications, Springer Verlag, Berlin, New York, 2007; J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt, M. Sterna, J. Weglarz, Handbook on Scheduling: from Theory to Practice, Springer Verlag, Berlin, New York, 2019. This series of fundamental books, with Prof. Blazewicz as the lead author, describes in a rigorous way the state-of-the-art of scheduling problems, which were presented in the context of proper mathematical and computational tools. The success of these monographs followed a thorough analysis of the problems in question. On the other hand, it was the result of several new models that were described and analysed, that directly followed practical applications. The total number of copies sold worldwide exceeds 10 000, while the number of citations reaches 3000 (GS).

J. Blazewicz, A. Hertz, D. Kobler, D. de Werra, On some properties of DNA graphs, Discrete Applied Mathematics 98, 1999, pp. 1-19 (83 cit.-GS, 41 cit.-WoS). This paper solved, in a formal way (using graph theory), an important problem in computational biology – DNA sequencing by hybridization (SBH). A new class of graphs – DNA graphs was introduced. This led to a solution of the long lasting dilemma of whether or not the DNA SBH problem can be solved in polynomial time. The paper had an impact also in graph theory, motivating researchers to study new classes of graphs. Later it led the team of Prof. Blazewicz to introduce a new isothermic DNA library, being the basis of an obtained national patent. What is more, the approaches based on the ideas presented in this paper, paved the path to the solution strategies for the Human Genome assembling (cf. the next paper). What is more, the experience and the fame gained by the team of prof. Blazewicz, when studied the above problem, resulted in receiving the grant worth 20 million euros from the Polish Research Council for a construction of the Genomic Map of Poland.

S. Swat, A. Laskowski, J. Badura, W. Frohmberg, P. Wojciechowski, A. Swiercz, M. Kasprzak, J. Blazewicz, Genome-scale de novo assembly using ALGA, Bioinformatics 37, 2021, pp. 1644-1651. This new paper uses the ideas presented in the above paper by Blazewicz et al.(1999) and develops the Alga algorithm being currently the best known worldwide for de novo Genome reconstruction. It is the main tool used by team of prof. Blazewicz to construct the Genomic Map of Poland.

M. Popenda, M. Szachniuk, M. Antczak, K. Purzycka, P. Lukasiak, N. Bartol, J. Blazewicz, R. Adamiak, Automated 3D structure composition for large RNAs, Nucleic Acid Research 40(14), 2012, e112 (572 cit.-GS, 394 cit.-WoS). This seminal paper presents an elegant and very efficient algorithm for the reconstruction of the tertiary structure of the RNA chains based on their linear sequences. The algorithm uses very advanced pattern recognition approaches for matching subchains and combines them to receive the resulting tertiary structure for a given sequence. The algorithm is the most frequently used tool by molecular biologists and biochemists working in that area. Its web version (https://rnacomposer.cs.put.poznan.pl) has over 6 million hits, exceeding by far all other web pages presenting similar tools.