CLSS: An Intelligent Crane Lorry Scheduling System

Companies that provide crane-lorry services are faced with the daily need to perform vehicle and driver allocation and scheduling. Many companies still do this manually due to the lack of suitable technologies. This manual approach is both time consuming and inaccurate and most probably will not lead to an optimized plan that can reduce operational costs. In this paper, we describe the design of a system called Crane Lorry Scheduling System (CLSS) that we have developed for the largest crane lorry company in Hong Kong. A crane lorry company is a company that provides lorries with different types of mounted crane equipment and drivers to service different types of moving and lifting jobs. CLSS is a Web-based application that streamlines communication with customers, subcontractors and employees/lorry drivers. We modeled the lorry-assignment problem as a constraint-satisfaction problem (CSP) algorithm, which we call the Crane Lorry Optimizing Engine (CLOE). CLOE was designed to be easily customizable to match the needs and requirements of different crane lorry companies. We experimented with two versions of CLOE, regular CLOE that finds best solutions and X-CLOE that finds optimal solutions. Results from our tests show that CLOE is faster and generates better quality plans than the manual approach.     

Information and pragmatic value-adding: Language games and information science

This paper discusses terms which are of mutual importance to the fields of information science and computer science. Specifically we discuss the notions of information and knowledge: their interrelationships as well as their differences, and the concept of value-adding. Concrete examples are used in the discussion.Rainer Kuhlen is professor of Information Science at the University of Konstanz.     

Interpretations of open default theories in non-monotonic logics

It is shown that the translation of an open default into a modal formula x(L(x)LM ₁ (x)...LM _m (x)w(x)) gives rise to an embedding of open default systems into non-monotonic logics.     

The Valid Use of Utility in Adaptive Real-Time Systems

Real-time systems that must adapt their behavior to changes in internal and external circumstances require flexibility in their scheduling. One approach that has been advocated for achieving this flexibility is called value-based scheduling, wherein services are distinguished based upon their current utility values. The main result of this paper is that the assumptions used in the assignment of these values must be matched with the way the values are used in scheduling. The key notion for ensuring this is the scale type of the value, in the sense defined by measurement theory. There are simple tests for meaningful uses of values based on their scale types, and we apply these tests to investigate the meaningfulness requirements of some commonly-used scheduling approaches.     

The conjoinability relation in Lambek calculus and linear logic

In 1958 J. Lambek introduced a calculusL of syntactic types and defined an equivalence relation on types: x y means that there exists a sequence x=x₁,...,x_n=y (n 1), such thatx _i x _i+1 or x_i+ x _i (1 i n). He pointed out thatx y if and only if there is joinz such thatx z andy z. This paper gives an effective characterization of this equivalence for the Lambeck calculiL andLP, and for the multiplicative fragments of Girard's and Yetter's linear logics. Moreover, for the non-directed Lambek calculusLP and the multiplicative fragment of Girard's linear logic, we present linear time algorithms deciding whether two types are equal, and finding a join for them if they are.The author was sponsored by project NF 102/62-356 (Structural and Semantic Parallels in Natural Languages and Programming Languages), funded by the Netherlands Organization for the Advancement of Research (N.W.O.).     

A multiprocessor working as a Fault-Tolerant cellular automaton

A memory-coupled multiprocessor—well suited to bit-wise operation—can be utilized to operate as a 1024 items cellular processing unit. Each processor is working on 32 bits and 32 such processors are combined to a multiprocessor. The information is stored in vertical direction, as it is defined and described in earlier papers [1] on vertical processing. The two-dimensional array (32 times 32 bits) is composed of the 32 bit-machine-words of the coupled processors on the one hand and of 32 processors in nearest-neighbour-topology on the other hand. The bit-wise cellular operation at one of the 1024 points is realized by the program of the processor—possibly assisted by appropriate microprogam sequences.Dedicated to Professor Willard L. Miranker on the occasion of his 60th birthday     

Minimization of norms and logarithmic norms by diagonal similarities

It is a commonly occurring problem to find good norms · or logarithmic norms (·) for a given matrix in the sense that they should be close to respectively the spectral radius (A) and the spectral abscissa (A). Examples may be the certification thatA is convergent, i.e. (A)A<1 or stable, i.e. (A)(A)<0. Often the ordinary norms do not suffice and one would like to try simple modifications of them such as using an ordinary norm for a diagonally transformed matrix. This paper treats this problem for some of the ordinary norms.

---

Minimisierung von Normen und Logarithmischen Normen durch Diagonale Transformationen

Zusammenfassung Ein oft vorkommendes praktisches Problem ist die Konstruktion von guten Normen · und logarithmischen Normen (·) für eine gegebene MatrixA. Mit gut wird dann verstanden, daß A den Spektralradius (A)=max |₁| und (A) die Spektralabszisse (A)=max Re _i gut approximieren. Beispiele findet man für konvergente Matrizen wo (A)A<1 gewünscht ist, und für stabile Matrizen wo (A)(A)<0 zu zeigen ist. Wir untersuchen hier, wie weit man mit Diagonaltransformationen und dengewöhnlichsten Normen kommen kann.

     

From Conditional Events to Conditional Measures: A New Axiomatic Approach

Our starting point is a definition of conditional event EH which differs from many seemingly similar ones adopted in the relevant literature since 1935, starting with de Finetti. In fact, if we do not assign the same third value u (undetermined) to all conditional events, but make it depend on EH, it turns out that this function t(EH) can be taken as a general conditional uncertainty measure, and we get (through a suitable – in a sense, compulsory – choice of the relevant operations among conditional events) the natural axioms for many different (besides probability) conditional measures.     

Geometrical Method of Scheduling in Project Management

Consideration was given to scheduling by the criterion for uniform use of resources. It was assumed that each job is executed by a unit resource. Two types of inter-job dependences were studied: finish–finish (one job cannot be completed until the other is completed) and finish–start (one job cannot be started until the other is not completed). To solve the problem, a geometrical method reducing solution to determining the shortest trajectory in a domain constructed from the network graph was proposed.     

Optimal multilayer channel routing with overlap

This paper presents algorithms for multiterminal net channel routing where multiple interconnect layers are available. Major improvements are possible if wires are able to overlap, and our generalized main algorithm allows overlap, but only on everyKth (K 2) layer. Our algorithm will, for a problem with densityd onL layers,L K + 3,provably use at most three tracks more than optimal: (d + 1)/L/K + 2 tracks, compared with the lower bound of d/L/K. Our algorithm is simple, has few vias, tends to minimize wire length, and could be used if different layers have different grid sizes. Finally, we extend our algorithm in order to obtain improved results for adjacent (K = 1) overlap: (d + 2)/2L/3 + 5 forL 7.This work was supported by the Semiconductor Research Corporation under Contract 83-01-035, by a grant from the General Electric Corporation, and by a grant at the University of the Saarland.     

Searching minimax game trees under memory space constraint

Games such as CHESS, GO and OTHELLO can be represented by minimax game trees. Among various search procedures to solve such game trees,- and SSS^* are perhaps most well known. Although it is proved that SSS^* explores only a subset of the nodes explored by-, - is commonly believed to be faster in real applications, since it requires very little memory space and hence its storage management cost is low. Contrary to this folklore, however, this paper reports, using the OTHELLO game as an example, that SSS^* is much faster than-. It is also demonstrated that SSS^* can be modified to make the required memory space controllable to some extent, while retaining the high efficiency of the original SSS^*.This research was partially supported by the Ministry of Education, Science and Culture of Japan, under a Scientific Grant-in-Aid.     

The dynamic clusters method in nonhierarchical clustering

Given a finite setE R ⁿ, the problem is to find clusters (or subsets of similar points inE) and at the same time to find the most typical elements of this set. An original mathematical formulation is given to the problem. The proposed algorithm operates on groups of points, called samplings (samplings may be called multiple centers or cores); these samplings adapt and evolve into interesting clusters. Compared with other clustering algorithms, this algorithm requires less machine time and storage. We provide some propositions about nonprobabilistic convergence and a sufficient condition which ensures the decrease of the criterion. Some computational experiments are presented.     

Unification in partially commutative semigroups

Unification algorithms have been constructed for semigroups and commutative semigroups. This paper considers the intermediate case of partially commutative semigroups. We introduce classesN and of such semigroups and justify their use. We present an equation-solving algorithm for any member of the classN. This algorithm is relative to having an algorithm to determine all non-negative solutions of a certain class of diophantine equations of degree 2 which we call -equations. The difficulties arising when attempting to solve equations in members of the class are discussed, and we present arguments that strongly suggest that unification in these semigroups is undecidable.     

Cockpit cognition: Education,the military and cognitive engineering

The goals of public education, as well as conceptions of human intelligence and learning, are undergoing a transformation through the application of military-sponsored information technologies and information processing models of human thought. Recent emphases in education on thinking skills, learning strategies, and computer-based technologies are the latest episodes in the postwar military agenda to engineer intelligent components, human and artificial, for the optimal performance of complex technological systems. Public education serves increasingly as a human factors laboratory and production site for this military enterprise, whose high performance technologies and command and control paradigms have also played central roles in the emergence of the information economy.Our final hope is to develop the brain as a natural resource ... Human intelligence will be the weapon of the future.Luis Alberto MachadoThis paper will also appear, under the title Mental Material inCyborg Worlds: The Military Information Society, eds. Les Levidow and Kevin Robins, London: Free Association Press, (in press).     

A Note on Scheduling Tall/Small Multiprocessor Tasks with Unit Processing Time to Minimize Maximum Tardiness

We study the scheduling situation where n tasks, subjected to release dates and due dates, have to be scheduled on m parallel processors. We show that, when tasks have unit processing times and either require 1 or m processors simultaneously, the minimum maximal tardiness can be computed in polynomial time. Two algorithms are described. The first one is based on a linear programming formulation of the problem while the second one is a combinatorial algorithm. The complexity status of this tall/small task scheduling problem P|r _i ,p _i =1, size _i {1,m}|T _max was unknown before, even for two processors.     

Prequential and Cross-Validated Regression Estimation

Prequential model selection and delete-one cross-validation are data-driven methodologies for choosing between rival models on the basis of their predictive abilities. For a given set of observations, the predictive ability of a model is measured by the model's accumulated prediction error and by the model's average-out-of-sample prediction error, respectively, for prequential model selection and for cross-validation. In this paper, given i.i.d. observations, we propose nonparametric regression estimators—based on neural networks—that select the number of hidden units (or neurons) using either prequential model selection or delete-one cross-validation. As our main contributions: (i) we establish rates of convergence for the integrated mean-squared errors in estimating the regression function using off-line or batch versions of the proposed estimators and (ii) we establish rates of convergence for the time-averaged expected prediction errors in using on-line versions of the proposed estimators. We also present computer simulations (i) empirically validating the proposed estimators and (ii) empirically comparing the proposed estimators with certain novel prequential and cross-validated mixture regression estimators.     

Quantum monadology: A world model to interpret quantum mechanics and relativity

In order to give a new insight to fundamental problems of quantum mechanics, relativity and mind, we propose a world model suggested from the monadology of Leibniz. The world is assumed to consist of monads which have their individuality and whose primary attribute is a space-time frame and not a position in spacetime. Each monad has freedom to change its frame. Accompanying this change, the world time is put forward, and the world state jumps off the unitary evolution. This model explains not only the measurement process of quantum mechanics but also the passing now and the origin of free will.     

Indecomposable local maps of tessellation automata

Indecomposable local maps of one-dimensional tessellation automata are studied. The main results of this paper are the following. (1) For any alphabet containing two or more symbols and for anyn 1, there exist indecomposable scope-n local maps over . (2) If is a finite field of prime order, then a linear scope-n local map over is indecomposable if and only if its associated polynomial is an irreducible polynomial of degreen – 1 over , except for a trivial case. (3) Result (2) is no longer true if is a finite field whose order is not prime.     

A principle of independence for binary tree searching

Summary When searching unsuccessfully for a fixed element in a random binary search tree, the number of comparisons made whose result is less is independent from the number of comparisons whose result is greater. This principle can be used to compute the mean and variance of the total number of comparisons involved in both a successful and an unsuccessful search.This work was supported in part by a Hertz Graduate Fellowship and by the Xerox Palo Alto Research Center.     

Learning to Play Chess Using Temporal Differences

In this paper we present TDLEAF(), a variation on the TD() algorithm that enables it to be used in conjunction with game-tree search. We present some experiments in which our chess program KnightCap used TDLEAF() to learn its evaluation function while playing on Internet chess servers. The main success we report is that KnightCap improved from a 1650 rating to a 2150 rating in just 308 games and 3 days of play. As a reference, a rating of 1650 corresponds to about level B human play (on a scale from E (1000) to A (1800)), while 2150 is human master level. We discuss some of the reasons for this success, principle among them being the use of on-line, rather than self-play. We also investigate whether TDLEAF() can yield better results in the domain of backgammon, where TD() has previously yielded striking success.