Machine scheduling with resource dependent processing times

We consider machine scheduling on unrelated parallel machines with the objective to minimize the schedule makespan. We assume that, in addition to its machine dependence, the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time, and the more of that resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelated parallel machine scheduling problem by adding a time-resource tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos. On the basis of an integer linear programming formulation for a relaxation of the problem, we use LP rounding techniques to allocate resources to jobs, and to assign jobs to machines. Combined with Graham’s list scheduling, we show how to derive a 4-approximation algorithm. We also show how to tune our approach to yield a 3.75-approximation algorithm. This is achieved by applying the same rounding technique to a slightly modified linear programming relaxation, and by using a more sophisticated scheduling algorithm that is inspired by the harmonic algorithm for bin packing. We finally derive inapproximability results for two special cases, and discuss tightness of the integer linear programming relaxations.     

Martingale characterization of limit distributions in the space of functions without discontinuities of second kind

Translated from Matematicheskie Zametki, Vol. 43, No. 5, pp. 692–700, May, 1988.     

Difficulties in building radiation-generated three-spin systems using spin-labeled luminophores

Aromatic compounds are well-known acceptors of primary radical ions that are formed under high-energy irradiation of nonpolar systems. Thus formed radical ion pairs recombine and produce magnetosensitive fluorescence, which helps study the short-lived radical ions. It was initially suggested that a simple introduction of a spin label into the original arene would allow an easy transition from two-spin to three-spin systems, retaining the experimental techniques available for radical pairs. However, it turned out that spin-labeled arenes often do not produce magnetosensitive fluorescence in the conditions of a conventional radiochemical experiment. To understand the effect of the introduced spin label, we synthesized a series of compounds with the general structure "stable 3-imidazoline radical-two-carbon bridge-naphthalene" as well as their diamagnetic analogues. By use of this set of acceptors, we determined the processes that ruin the observed signal and established their connection with the chemical structure of the compound. We found that the compounds with flexible (saturated) two-carbon bridges between the luminophore and the stable radical moieties exist in solution in folded conformation, which leads to suppression of luminescence from naphthalene due to efficient through-space exchange quenching of the excited state by the radical. Increasing the rigidity of the bridge by introducing the double bond drastically increases the reactivity of the extended pi-system. In these compounds, the energy released upon recombination is spent in radiationless processes of chemical transformations both at the stage of the radical ion and at the stage of the electronically excited molecule.     

Structural properties of optimal schedules with preemption

Scheduling problems with preemption are considered, where each operation can be interrupted and resumed later without any penalty. We investigate some basic properties of their optimal solutions. When does an optimal schedule exist (provided that there are feasible schedules)? When does it have a finite/polynomial number of interruptions? Do they occur at integral/rational points only? These theoretical questions are also of practical interest, since structural properties can be used to reduce the search space in a practical scheduling application. In this paper we answer some of these basic questions for a rather general scheduling model (including, as the special cases, the classicalmodels such as parallelmachine scheduling, shop scheduling, and resource constrained project scheduling) and for a large variety of the objective functions including nearly all known. For some two special cases of objective functions (including, however, all classical ones), we prove the existence of an optimal solution with a special “rational structure.” An important consequence of this property is that the decision versions of these optimization scheduling problems belong to class NP.     

A Note on Permutation Flow Shop Problem

In this paper we present two approximation algorithms for the permutation flow shop problem with makespan objective. The first algorithm has an absolute performance guarantee, the second one is an $O(\sqrt {m{\text{ log }}m} )$ -approximation algorithm. The last result is almost best possible approximation algorithm which can be obtained using the trivial lower bound (maximum of the maximum machine load and the maximum job length) (Potts, Shmoys, and Williamson, 1991).     

Benchmarking ordering techniques for nonserial dynamic programming

Five ordering algorithms for the nonserial dynamic programming algorithm for solving sparse discrete optimization problems are compared in this paper. The benchmarking reveals that the ordering of the variables has a significant impact on the run-time of these algorithms. In addition, it is shown that different orderings are most effective for different classes of problems. Finally, it is shown that, amongst the algorithms considered here, heuristics based on maximum cardinality search and minimum fill-in perform best for solving the discrete optimization problems considered in this paper.     

A (2+)-approximation algorithm for the generalized preemptive open shop problem with minsum objective

In this paper we consider a generalized version of the classical preemptive open shop problem with sum of weighted job completion times objective. The main result is a (2+)-approximation algorithm for this problem. In the last section we also discuss the possibility of improving our algorithm.     

Discretization orders for distance geometry problems

Given a weighted, undirected simple graph G = (V, E, d) (where \({d:E\to\mathbb{R}_+}\)), the distance geometry problem (DGP) is to determine an embedding \({x:V\to\mathbb{R}^K}\) such that \({\forall \{i,j\} \in E\;\|x_i-x_j\|=d_{ij}}\) . Although, in general, the DGP is solved using continuous methods, under certain conditions the search is reduced to a discrete set of points. We give one such condition as a particular order on V. We formalize the decision problem of determining whether such an order exists for a given graph and show that this problem is NP-complete in general and polynomial for fixed dimension K. We present results of computational experiments on a set of protein backbones whose natural atomic order does not satisfy the order requirements and compare our approach with some available continuous space searches.