The open shop scheduling problem with a given sequence of jobs on one machine

The paper considers the open shop scheduling problem to minimize the make-span, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not allowed, the problem is NP-hard in the strong sense if the number of machines is variable, and is NP-hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5/4 times the optimal value. We also show that the two-machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 705–731, 1998

Modelling the nano-scale phenomena in condensed matter physics via computer-based numerical simulations

A review of the atomistic modelling of the behaviour of nano-scale structures and processes via molecular dynamics (MD) simulation method of a canonical ensemble is presented. Three areas of application in condensed matter physics are considered. We focus on the adhesive and indentation properties of the solid surfaces in nano-contacts, the nucleation and growth of nano-phase metallic and semi-conducting atomic and molecular films on supporting substrates, and the nano- and multi-scale crack propagation properties of metallic lattices. A set of simulations selected from these fields are discussed, together with a brief introduction to the methodology of the MD simulation. The pertinent inter-atomic potentials that model the energetics of the metallic and semi-conducting systems are also given.