In this paper, we consider a class of scheduling problems that are among the fundamental optimization problems in operations research. More specifically, we deal with a particular version called job shop scheduling with unit length tasks. Using the results of Hromkovič, Mömke, Steinhöfel, and Widmayer presented in their work Job Shop Scheduling with Unit Length Tasks: Bounds and Algorithms, we analyze the problem setting for 2 jobs with an unequal number of tasks. We contribute a deterministic algorithm which achieves a vanishing delay in certain cases and a randomized algorithm with a competitive ratio tending to 1. Furthermore, we investigate the problem with 3 jobs and we construct a randomized online algorithm which also has a competitive ratio tending to 1.

Given two trees (a target T and a pattern P) and a natural number w, window embedded subtree problems consist in deciding whether P occurs as an embedded subtree of T and/or finding the number of size (at most) w windows of T which contain pattern P as an embedded subtree. P is an embedded subtree of T if P can be obtained by deleting some nodes from T (if a node v is deleted, all edges adjacent to v are also deleted, and outgoing edges are replaced by edges going from the parent of v (if it exists) to the children of v). Deciding whether P is an embedded subtree of T is known to be NP-complete. Our algorithms run in time O(|T|22|P|) where |T| (resp. |P|) is the size of T (resp. P).

We study translations of dyadic first-order sentences into equalities between relationalexpressions. The proposed translation techniques (which work also in the conversedirection) exploit a graphical representation of formulae in a hybrid of the twoformalisms. A major enhancement relative to previous work is that we can cope with therelational complement construct and with the negation connective. Complementation ishandled by adopting a Smullyan-like uniform notation to classify and decompose relationalexpressions; negation is treated by means of a generalized graph-representation offormulae in ℒ+, and through a series of graph-transformation rules whichreflect the meaning of connectives and quantifiers.