A polynomial algorithm for the three-machine open shop with a bottleneck machine

The paper considers the three‐machine open shop scheduling problem to minimize themakespan. It is assumed that each job consists of at most two operations, one of which is tobe processed on the bottleneck machine, the same for all jobs. A new lower bound on theoptimal makespan is derived, and a linear‐time algorithm for finding an optimalnon‐preemptive schedule is presented.

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.

Micro-mechanical parameterisations for continuum modelling of granular material using the discrete element method

The present work uses the discrete element method (DEM) to describe assemblies of particulate bulk materials. Working numerical descriptions of entire processes using this scheme are infeasible because of the very large number of elements (1012 or more in a moderately sized industrial silo). However it is possible to capture much of the essential bulk mechanics through selective DEM on important regions of an assembly, thereafter using the information in continuum numerical descriptions of particulate processes. The continuum numerical model uses population balances of the various components in bulk solid mixtures. It depends on constitutive relationships for the internal transfer, creation and/or destruction of components within the mixture. In this paper we show the means of generating such relationships for two important flow phenomena – segregation whereby particles differing in some important property (often size) separate into discrete phases, and degradation, whereby particles break into sub-elements, through impact on each other or shearing. We perform DEM simulations under a range of representative conditions, extracting the important parameters for the relevant transfer, creation and/or destruction of particles in certain classes within the assembly over time. Continuum predictions of segregation and degradation using this scheme are currently being successfully validated against bulk experimental data and are beginning to be used in schemes to improve the design and operation of bulk solids process plant.

A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date

We develop a fully polynomial-time approximation scheme (FPTAS) for minimizing the weighted total tardiness on a single machine, provided that all due dates are equal. The FPTAS is obtained by converting an especially designed pseudopolynomial dynamic programming algorithm.