Search for: All records

Uncertainty is an omnipresent issue in real-world optimization problems. This paper studies a fundamental problem concerning uncertainty, known as the β-robust scheduling problem. Given a set of identical machines and a set of jobs whose processing times follow a normal distribution, the goal is to assign jobs to machines such that the probability that all the jobs are completed by a given common due date is maximized. We give the first systematic study on the complexity and algorithms for this problem. A strong negative result is shown by ruling out the existence of any polynomial-time algorithm with a constant approximation ratio for the general problem unless P=NP. On the positive side, we provide the first FPT-AS (fixed parameter tractable approximation scheme) parameterized by the number of different kinds of jobs, which is a common parameter in scheduling problems. It returns a solution arbitrarily close to the optimal solution, provided that the job processing times follow a few different types of distributions. We further complement the theoretical results by implementing our algorithm. The experiments demonstrate that by choosing an appropriate approximation ratio, the algorithm can efficiently compute a near-optimal solution. 

Persistent spin texture (PST) is the property of some materials to maintain a uniform spin configuration in the momentum space. This property has been predicted to support an extraordinarily long spin lifetime of carriers promising for spintronics applications. Here, we predict that there exists a class of noncentrosymmetric bulk materials, where the PST is enforced by the nonsymmorphic space group symmetry of the crystal. Around certain high symmetry points in the Brillouin zone, the sublattice degrees of freedom impose a constraint on the effective spin–orbit field, which orientation remains independent of the momentum and thus maintains the PST. We illustrate this behavior using density-functional theory calculations for a handful of promising candidates accessible experimentally. Among them is the ferroelectric oxide BiInO₃—a wide band gap semiconductor which sustains a PST around the conduction band minimum. Our results broaden the range of materials that can be employed in spintronics.