In the paper, the problem of the genome mapping of DNA molecules, is presented. In particular, the new approach — the Simplified Partial Digest Problem (SPDP), is analyzed. This approach, although easy in laboratory implementation and robust with respect to measurement errors, when formulated in terms of a combinatorial search problem, is proved to be strongly NP-hard for the general error-free case. For a subproblem of the SPDP, a simple O()-time algorithm is given, where is a number of restriction...
In this paper, open shop scheduling problems with limited machine availability are studied. Such a limited availability of machines may appear in many real-life situations, e.g. as preventive maintenance activities. Three types of jobs are distinguished: non-preemptable, resumable and preemptable. An operation of a resumable job if not completed before a non-availability period of a machine may be suspended and continued without additional cost when the machine becomes available. In the paper, results...
In this paper, open shop scheduling problems with limited machine availability
are studied. Such a limited availability of machines may appear in
many real-life situations, as preventive maintenance activities.
Three types of jobs are distinguished: non-preemptable,
resumable and preemptable. An operation of a resumable job if not completed
before a non-availability period of a machine may be suspended and continued
without additional cost when the machine becomes available.
In the paper, results...
In the paper, the problem of the genome mapping of DNA molecules, is presented. In particular, the new approach — the Simplified Partial Digest Problem (SPDP), is analyzed. This approach, although easy in laboratory implementation and robust with respect to measurement errors, when formulated in terms of a combinatorial search problem, is proved to be strongly NP-hard for the general error-free case. For a subproblem of the SPDP, a simple O(log)-time algorithm is given, where is a number of restriction...
In this work scheduling multiprocessor tasks on two parallel identical processors is considered. Multiprocessor tasks can be executed by more than one processor at the same moment of time. We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness. Cases with ready times, due-dates and precedence constraints are discussed.
BAliBASE is one of the most widely used benchmarks for multiple sequence alignment programs. The accuracy of alignment methods is measured by bali score-an application provided together with the database. The standard accuracy measures are the Sum of Pairs (SP) and the Total Column (TC). We have found that, for non-core block columns, results calculated by bali score are different from those obtained on the basis of the formal definitions of the measures. We do not claim that one of these measures...
In this work scheduling multiprocessor tasks on two parallel identical processors is considered.
Multiprocessor tasks can be executed by more than one processor
at the same moment of time.
We analyze scheduling unit execution time and preemptable tasks
to minimize schedule length and maximum lateness.
Cases with ready times, due-dates and precedence constraints
are discussed.
A concept of an Orderly Colored Longest Path (OCLP) refers to the problem of finding the longest path in a graph whose edges are colored with a given number of colors, under the constraint that the path follows a predefined order of colors. The problem has not been widely studied in the previous literature, especially for more than two colors in the color arrangement sequence. The recent and relevant application of OCLP is related to the interpretation of Nuclear Magnetic Resonance experiments for...
The coupled tasks scheduling problem is a class of scheduling problems introduced for beam steering software of sophisticated radar devices, called phased arrays. Due to increasing popularity of such radars, the importance of coupled tasks scheduling is constantly growing. Unfortunately, most of the coupled tasks problems are NP-hard, and only a few practically usable algorithms for such problems were found. This paper provides a survey of already known complexity results of various variants of...
Determining amino acid sequences of protein molecules is one of the most important issues in molecular biology. These
sequences determine protein structure and functionality. Unfortunately, direct biochemical methods for reading amino
acid sequences can be used for reading short sequences only. This is the reason, which makes peptide assembly algorithms
an important complement of these methods. In this paper, a genetic algorithm solving the problem of short amino acid sequence
assembly is presented....
A high number of Internet shops makes it difficult for a customer to review manually all the available offers and select optimal outlets for shopping. A partial solution to the problem is brought by price comparators which produce price rankings from collected offers. However, their possibilities are limited to a comparison of offers for a single product requested by the customer. The issue we investigate in this paper is a multiple-item multiple-shop optimization problem, in which total expenses...
An increasing number of known RNA 3D structures contributes to the recognition of various RNA families and identification of their features. These tasks are based on an analysis of RNA conformations conducted at different levels of detail. On the other hand, the knowledge of native nucleotide conformations is crucial for structure prediction and understanding of RNA folding. However, this knowledge is stored in structural databases in a rather distributed form. Therefore, only automated methods...
Internet shopping has been one of the most common online activities, carried out by millions of users every day. As the number of available offers grows, the difficulty in getting the best one among all the shops increases as well. In this paper we propose an integer linear programming (ILP) model and two heuristic solutions, the MinMin algorithm and the cellular processing algorithm, to tackle the Internet shopping optimization problem with delivery costs. The obtained results improve those achieved...
Download Results (CSV)