The block relocation problem, which is also known as the container relocation problem, is an optimization problem to find an optimal sequence of operations for retrieving blocks (containers) from a container yard in a given order. The objective function to be minimized is the number of necessary relocations. In this study, we propose an efficient exact algorithm for two variants of the block relocation problem, those with distinct and duplicate retrieval priorities. In the former problem, the retrieval order of blocks is uniquely provided, whereas in the latter problem, it is given only among groups of blocks. The primary contribution of this study is a tighter lower bound of the number of relocations than existing ones. This enables us to construct a faster branch-and-bound algorithm. Its effectiveness is demonstrated by extensive numerical experiments.

In this paper efficient exact algorithms are proposed for the planted ( l, d)-motif search problem. This problem is to find all motifs of length l that are planted in each input string with at most d mismatches. The "quorum" version of this problem is also treated in this paper to find motifs planted not in all input strings but in at least q input strings. The proposed algorithms are based on the previous algorithms called qPMSPruneI and qPMS7 that traverse a search tree starting from a l-length substring of an input string. To improve these previous algorithms, several techniques are introduced, which contribute to reducing the computation time for the traversal. In computational experiments, it will be shown that the proposed algorithms outperform the previous algorithms.

The purpose of this study is to model the car operation problem in multi-car elevator systems. The multi-car elevator system is such a system that more than one car is installed in every elevator shaft. To take its full advantage, intelligent car operation is necessary so that neither collisions nor reversal occurs. In this paper we will propose a mathematical model for the car operation problem in multi-car elevator systems. First, it will be formulated as a mixed-integer linear programming problem, and next a branch-and-bound algorithm will be proposed. Then, the validity of the model and the effectiveness of the algorithm will be examined by numerical experiments.

The closest string problem that arises in both computational biology and coding theory is to find a string that minimizes the maximum Hamming distance from a given set of strings. This study proposes an efficient heuristic algorithm for this NP-hard problem. The key idea is to apply the Lagrangian relaxation technique to the problem formulated as an integer programming problem. This enables us to decompose the problem into trivial subproblems corresponding to each position of the strings. Furthermore, a feasible solution can be easily obtained from a solution of the relaxation. Based on this, a heuristic algorithm is constructed by combining a Lagrangian multiplier adjustment procedure and a tabu search. Numerical experiments will show the effectiveness of the proposed algorithm.

The purpose of this study is to extend the well-known decomposition theorem for the single-machine total tardiness problem to the case when a precedence constraint between a pair of jobs is set. Since the decomposition theorem forms the basis of strict solution algorithms for the ordinary single-machine total tardiness problem, it is expected that we can construct efficient solution algorithms by the extended decomposition theorem even for the problem with a precedence constraint. We also extend the elimination rules to restrict the possible job positions in an optimal schedule that are also utilized in strict solution algorithms. Then, we construct a simple strict solution algorithm for our problem and show the effectiveness of our results by numerical experiments.

In this paper we propose a branch-and-bound algorithm for the single-machine earliness-tardiness scheduling problem where weights for earliness and tardiness are independent of jobs. Here, machine idle times are allowed. In our branch-and-bound algorithm, the search tree is generated by fixing the processing order of jobs from the first to the last, or, from the last to the first. To improve the efficiency of the algorithm, we propose new lower bounds. We also show dominance properties that are utilized both for reducing branches in the search tree and for improving the lower bounds. Then, we show the effectiveness of our algorithm by numerical experiments.

This paper presents methods for increasing the efficiency of operating systems in plural virtual machines to a near-native performance level. The proposed direct execution methods support direct I/O execution for plural virtual machines, that is, the V = R virtual machine, and the V = Resi virtual machines, including both I/O instruction issuances and I/O interrupts. All V = Resi virtual machines have an entirely resident memory and their real addresses are translated into those of the host simply by adding a constant, α(≠ 0), which constitutes a starting address given to each V = Resi virtual machine. The V = R virtual machine has almost the same memory attribute as the V = Resi VM except for α = 0. Only one V = R virtual machine can be present in all virtual machines. The experimental results obtained confirm that a near-native performance level, that is, a level exceeding 90 percent of native performance, can be realized for the V = R virtual machine as well as for the V = Resi virtual machines.