Shop-scheduling problems with fixed and non-fixed machine orders of the jobs

The paper deals with the determination of an optimal schedule for the so-called mixed shop problem when the makespan has to be minimized. In such a problem, some jobs have fixed machine orders (as in the job-shop), while the operations of the other jobs may be processed in arbitrary order (as in the open-shop). We prove binary NP-hardness of the preemptive problem with three machines and three jobs (two jobs have fixed machine orders and one may have an arbitrary machine order). We answer all other remaining open questions on the complexity status of mixed-shop problems with the makespan criterion by presenting different polynomial and pseudopolynomial algorithms.

Deriving explanations from partial temporal information

The representation and manipulation of natural human understanding of temporal phenomena is a fundamental field of study in Computer Science, which aims both to emulate human thinking, and to use the methods of human intelligence to underpin engineering solutions. In particular, in the domain of Artificial Intelligence, temporal knowledge may be uncertain and incomplete due to the unavailability of complete and absolute temporal information. This paper introduces an inferential framework for deriving logical explanations from partial temporal information. Based on a graphical representation which allows expression of both absolute and relative temporal knowledge in incomplete forms, the system can deliver a verdict to the question if a given set of statements is temporally consistent or not, and provide understandable logical explanation of analysis by simplified contradiction and rule based reasoning.

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401–410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worst-case performance ratio of 2+ε. © 2008 Elsevier B.V. All rights reserved.

Radio propagation modeling for capacity optimization in wireless relay MIMO systems with partial CSI

The enormous growth of wireless communication systems makes it important to evaluate the capacity of such channels. Multiple Input Multiple Output (MIMO) wireless communication systems are shown to yield significant performance improvement to data rates when compared to the traditional Single Input Single Output (SISO) wireless systems. The benefits of multiple antenna elements at the transmitter and receiver have become necessary to the research and the development of the next generation of mobile communication systems. In this paper we propose the use of Relaying MIMO wireless communication systems for use over long throughput. We investigate how Relays can be used in a "demodulate-and-forward" operation when the transmitter is equipped with spatially correlated multiple antenna elements and the receiver has only partial knowledge of the statistics of the channel. We show that Relays between the source and destination nodes of a wireless communication system in MIMO configuration improve the throughput of the system when compared to the typical MIMO systems, or achieve the desired channel capacity with significantly lower power resources needed.