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

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.

Complexity of mixed shop scheduling problems: A survey

We survey recent results on the computational complexity of mixed shop scheduling problems. In a mixed shop, 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). The main attention is devoted to establishing the boundary between polynomially solvable and NP-hard problems. When the number of operations per job is unlimited, we focus on problems with a fixed number of jobs.

Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation

We consider various single machine scheduling problems in which the processing time of a job depends either on its position in a processing sequence or on its start time. We focus on problems of minimizing the makespan or the sum of (weighted) completion times of the jobs. In many situations we show that the objective function is priority-generating, and therefore the corresponding scheduling problem under series-parallel precedence constraints is polynomially solvable. In other situations we provide counter-examples that show that the objective function is not priority-generating.

Optimisation quadratique en variables binaires : quelques résultats et techniques

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Multi-channel curve crossing problems: analytically solvable model

We have proposed a general method for finding the exact analytical solution for the multi-channel curve crossing problem in the presence of delta function couplings. We have analysed the case where aa potential energy curve couples to a continuum (in energy) of the potential energy curves.

A New Class of Exactly Solvable Interacting Fermion Models in One Dimension

We investigate a model containing two species of one-dimensional fermions interacting via a gauge field determined by the positions of all particles of the opposite species. The model can be salved exactly via a simple unitary transformation. Nevertheless, correlation functions exhibit nontrivial interaction-dependent exponents. A similar model defined on a lattice is introduced and solved. Various generalizations, e.g., to the case of internal symmetries of the fermions, are discussed. The present treatment also clarifies certain aspects of Luttinger's original solution of the "Luttinger model."

Galois Theory and Solvable Equations of Prime Degree

In this article we review classical and modern Galois theory with historical evolution and prove a criterion of Galois for solvability of an irreducible separable polynomial of prime degree over an arbitrary field k and give many illustrative examples.

An exactly solvable four transition point model

Heavy particle collisions, in particular low-energy ion-atom collisions, are amenable to semiclassical JWKB phase integral analysis in the complex plane of the internuclear separation. Analytic continuation in this plane requires due attention to the Stokes phenomenon which parametrizes the physical mechanisms of curve crossing, non-crossing, the hybrid Nikitin model, rotational coupling and predissociation. Complex transition points represent adiabatic degeneracies. In the case of two or more such points, the Stokes constants may only be completely determined by resort to the so-called comparison- equation method involving, in particular, parabolic cylinder functions or Whittaker functions and their strong-coupling asymptotics. In particular, the Nikitin model is a two transition-point one-double-pole problem in each half-plane corresponding to either ingoing or outgoing waves. When the four transition points are closely clustered, new techniques are required to determine Stokes constants. However, such investigations remain incomplete, A model problem is therefore solved exactly for scattering along a one-dimensional z-axis. The energy eigenvalue is b(2)-a(2) and the potential comprises -z(2)/2 (parabolic) and -a(2) + b(2)/2z(2) (centrifugal/centripetal) components. The square of the wavenumber has in the complex z-plane, four zeros each a transition point at z = +/-a +/- ib and has a double pole at z = 0. In cases (a) and (b), a and b are real and unitarity obtains. In case (a) the reflection and transition coefficients are parametrized by exponentials when a(2) + b(2) > 1/2. In case (b) they are parametrized by trigonometrics when a(2) + b(2) <1/2 and total reflection is achievable. In case (c) a and b are complex and in general unitarity is not achieved due to loss of flux to a continuum (O'Rourke and Crothers, 1992 Proc. R. Sec. 438 1). Nevertheless, case (c) coefficients reduce to (a) or (b) under appropriate limiting conditions. Setting z = ht, with h a real constant, an attempt is made to model a two-state collision problem modelled by a pair of coupled first-order impact parameter equations and an appropriate (T) over tilde-tau relation, where (T) over tilde is the Stueckelberg variable and tau is the reduced or scaled time. The attempt fails because (T) over tilde is an odd function of tau, which is unphysical in a real collision problem. However, it is pointed out that by applying the Kummer exponential model to each half-plane (O'Rourke and Crothers 1994 J. Phys. B: At. Mel. Opt. Phys. 27 2497) the current model is in effect extended to a collision problem with four transition points and a double pole in each half-plane. Moreover, the attempt in itself is not a complete failure since it is shown that the result is a perfect diabatic inelastic collision for a traceless Hamiltonian matrix, or at least when both diagonal elements are odd and the off-diagonal elements equal and even.

The solvable Lie group N_{6, 28}: an example of an almost C_0(\mathcal{K})-C*-algebra

Motivated by the description of the C*-algebra of the affine automorphism group N6,28 of the Siegel upper half-plane of degree 2 as an algebra of operator fields defined over the unitary dual View the MathML source of the group, we introduce a family of C*-algebras, which we call almost C0(K), and we show that the C*-algebra of the group N6,28 belongs to this class.

Short-time behaviour of demand and price viewed through an exactly solvable model for heterogeneous interacting market agents

We introduce a stochastic heterogeneous interacting-agent model for the short-time non-equilibrium evolution of excess demand and price in a stylized asset market. We consider a combination of social interaction within peer groups and individually heterogeneous fundamentalist trading decisions which take into account the market price and the perceived fundamental value of the asset. The resulting excess demand is coupled to the market price. Rigorous analysis reveals that this feedback may lead to price oscillations, a single bounce, or monotonic price behaviour. The model is a rare example of an analytically tractable interacting-agent model which allows LIS to deduce in detail the origin of these different collective patterns. For a natural choice of initial distribution, the results are independent of the graph structure that models the peer network of agents whose decisions influence each other. (C) 2009 Elsevier B.V. All rights reserved.