Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is NP-hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst-case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two-machine flow shop and the open shop problems with a single server are also shown to be NP-hard in the strong sense. However, we reduce the two-machine flow shop no-wait problem with a single server to the Gilmore-Gomory traveling salesman problem and solve it in polynomial time. (c) 2000 John Wiley & Sons, Inc.

[Book review] Peter Reimann and Hans Spada (eds), Learning in Humans and Machines: Towards an Interdisciplinary Learning Science

Review of: Peter Reimann and Hans Spada (eds), Learning in Humans and Machines: Towards an Interdisciplinary Learning Science, Pergamon. (1995). ISBN: 978-0080425696

Virtual manufacturing and design in the real world - implementation and scalability on HPPC systems

Virtual manufacturing and design assessment increasingly involve the simulation of interacting phenomena, sic. multi-physics, an activity which is very computationally intensive. This chapter describes an attempt to address the parallel issues associated with a multi-physics simulation approach based upon a range of compatible procedures operating on one mesh using a single database - the distinct physics solvers can operate separately or coupled on sub-domains of the whole geometric space. Moreover, the finite volume unstructured mesh solvers use different discretization schemes (and, particularly, different ‘nodal’ locations and control volumes). A two-level approach to the parallelization of this simulation software is described: the code is restructured into parallel form on the basis of the mesh partitioning alone, that is, without regard to the physics. However, at run time, the mesh is partitioned to achieve a load balance, by considering the load per node/element across the whole domain. The latter of course is determined by the problem specific physics at a particular location.

The specification and design of an interactive virtual environment for use in teacher training

The original concept was to create a 'simulation' which would provide trainee teachers, specializing in Information and Communications Technology (ICT) with the opportunity to explore a primary school environment. Within the simulation, factors affecting the development and implementation of ICT would be modelled so that trainees would be able to develop the skills, knowledge and understanding necessary to identify appropriate strategies to overcome the limitations. To this end, we have developed Allsorts Primary - the prototype of a simulated interactive environment, representing a typical primary school

Scheduling parallel dedicated machines under a single non-shared resource

The scheduling problem of minimizing the makespan for m parallel dedicated machines under single resource constraints is considered. For different variants of the problem the complexity status is established. Heuristic algorithms employing the so-called group technology approach are presented and their worst-case behavior is examined. Finally, a polynomial time approximation scheme is presented for the problem with fixed number of machines.

Scheduling problems for parallel dedicated machines under multiple resource constraints

The paper considers scheduling problems for parallel dedicated machines subject to resource constraints. A fairly complete computational complexity classification is obtained, a number of polynomial-time algorithms are designed. For the problem with a fixed number of machines in which a job uses at most one resource of unit size a polynomial-time approximation scheme is offered.

Exploiting virtual prototyping for reliability assessment

Products manufactured by the electronics sector are having a major impact in telecommunications, transportation space applications, biomedical applications, consumer products, intelligent hand held devices, and of course,the computer. Demands from end-users in terms of greater product functionality, adoption of environmentally friendly materials, and further miniaturization continually pose several challenges to electronics companies. In the context of electronic product design and manufacture, virtual prototying software tools are allowing companies to dramatically reduce the number of phsysical prototypes and design iterations required in product development and hence reduce costs and time to market. This paper details of the trends in these technolgies and provides an example of their use for flip-chip assembly technology.

Powering the virtual university with standard portal technology

This article describes ongoing research on developing a portal framework based on the OASIS Web Services for Remote Portlets (WSRP) standard for integration of Web-based education contents and services made available through a model for a European Networked University. We first identify the requirements for such a framework that supports integration at the presentation level and collaboration in developing and updating study programmes and course materials. We then outline the architecture design, and report on the initial implementation and preliminary evaluation.

The ParaWise expert assistant - widening accessibility to efficient and scalable tool Generated OpenMP code

Despite the apparent simplicity of the OpenMP directive shared memory programming model and the sophisticated dependence analysis and code generation capabilities of the ParaWise/CAPO tools, experience shows that a level of expertise is required to produce efficient parallel code. In a real world application the investigation of a single loop in a generated parallel code can soon become an in-depth inspection of numerous dependencies in many routines. The additional understanding of dependencies is also needed to effectively interpret the information provided and supply the required feedback. The ParaWise Expert Assistant has been developed to automate this investigation and present questions to the user about, and in the context of, their application code. In this paper, we demonstrate that knowledge of dependence information and OpenMP are no longer essential to produce efficient parallel code with the Expert Assistant. It is hoped that this will enable a far wider audience to use the tools and subsequently, exploit the benefits of large parallel systems.

Experience of using a CFD code for estimating the noise generated by gusts along the sun-roof of a car

The problem to be examined here is the fluctuating pressure distribution along the open cavity of the sun-roof at the top of a car compartment due to gusts passing over the sun-roof. The aim of this test is to investigate the capability of a typical commercial CFD package, PHOENICS, in recognising pressure fluctuations occurring in an important automotive industrial problem. In particular to examine the accuracy of transporting pulsatory gusts traveling along the main flow through the use of finite volume methods with higher order schemes in the numercial solutins of the unsteady compressible Navier-Stokes equations. The Helmholtz equation is used to solve the sound distribution inside the car compartment, resulting from the externally induced fluctuations.

Support vector machines for regression and applications to software quality prediction

Software metrics are the key tool in software quality management. In this paper, we propose to use support vector machines for regression applied to software metrics to predict software quality. In experiments we compare this method with other regression techniques such as Multivariate Linear Regression, Conjunctive Rule and Locally Weighted Regression. Results on benchmark dataset MIS, using mean absolute error, and correlation coefficient as regression performance measures, indicate that support vector machines regression is a promising technique for software quality prediction. In addition, our investigation of PCA based metrics extraction shows that using the first few Principal Components (PC) we can still get relatively good performance.

Scheduling parallel dedicated machines with the speeding-up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two-machine problem is NP-hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst-case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple-choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008

Preemptive scheduling on uniform parallel machines with controllable job processing times

In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan.

Virtual assignments: breach of covenant against parting with or sharing of possession

Comments on the Chancery Division decision in Clarence House Ltd v National Westminster Bank Plc on whether the alienation covenant in a lease of commercial premises had been breached by the tenant effecting a virtual assignment of it, under which all the economic benefits and burdens of the lease were transferred to a third party without there being any actually assignment of the leasehold interest or change in occupancy.