Heuristics for the two-stage job shop scheduling problem with a bottleneck machine

The paper considers the job shop scheduling problem to minimize the makespan. It is assumed that each job consists of at most two operations, one of which is to be processed on one of m⩾2 machines, while the other operation must be performed on a single bottleneck machine, the same for all jobs. For this strongly NP-hard problem we present two heuristics with improved worst-case performance. One of them guarantees a worst-case performance ratio of 3/2. The other algorithm creates a schedule with the makespan that exceeds the largest machine workload by at most the length of the largest operation.

Two-stage open shop scheduling with a bottleneck machine

It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless P6≠NP. However, this result holds only if the instance of the problem contains jobs consisting of at least three operations. This paper considers the open shop scheduling problem, provided that each job consists of at most two operations, one of which is to be processed on one of the m⩾2 machines, while the other operation must be performed on the bottleneck machine, the same for all jobs. For this NP-hard problem we present a heuristic algorithm and show that its worst-case performance ratio is 5/4.

An integrated study (geochemistry, stable oxygen and carbon isotopes, nannofossils, planktonic foraminifera, inoceramid bivalves, ammonites and crinoids) of the Waxahachie Dam Spillway section, north Texas: a possible boundary stratotype for the base of the Campanian Stage

The spillway of Lake Waxahachie, Ellis County (Texas), exposes a > 17 m section of the Hutchins Member of the Austin Chalk Group, un-conformably overlain by Taylor Clay. The Austin sequence was regarded as a potential Global Stratotype Section for the base of the Campanian Stage at the 1995 Brussels meeting on Cretaceous Stage boundaries, with the last occurrence of the crinoid Marsupites testudinarius (von Schlotheim, 1820) as the potential boundary marker. An integrated study of the geochemistry, stable carbon and oxgen isotopes, nannofossils, planktonic foraminifera, inoceramid bivalves, ammonites and crinoids of this section place the last occurrence of M. testudinarius in a matrix of eighteen ancillary biostratigraphic markers, while the boundary can also be recognised on the basis of a delta C-13 excursion that can, in principle, be detected globally in marine sediments. A new forma of the crinoid Marsupites testudinarius is introduced. The Waxahachie section fulfils sufficient geological criteria as to be an excellent candidate GSSP for the base of the Campanian Stage, if problems of ownership and access to the section can be resolved.