We introduce a parallel machine scheduling problem in which the processing times of jobs are not given in advance but are determined by a system of linear constraints. The objective is to minimize the makespan, i.e., the maximum job completion time among all feasible choices. This novel problem is motivated by various real-world application scenarios. We discuss the computational complexity and algorithms for various settings of this problem. In particular, we show that if there is only one machine with an arbitrary number of linear constraints, or there is an arbitrary number of machines with no more than two linear constraints, or both the number of machines and the number of linear constraints are fixed constants, then the problem is polynomial-time solvable via solving a series of linear programming problems. If both the number of machines and the number of constraints are inputs of the problem instance, then the problem is NP-Hard. We further propose several approximation algorithms for the latter case.

No abstract uploaded!

No abstract uploaded!

A Riemannian or Finsler metric on a compact manifoldM gives rise to a length function on the free loop space M, whose critical points are the closed geodesics in the given metric. If X is a homology class on M, the “minimax” critical level cr(X) is a critical value. Let M be a sphere of dimension > 2, and fix a metric g and a coefficient field G. We prove that the limit as deg(X) goes to infinity of cr(X)/ deg(X) exists. We call this limit = (M, g,G) the global mean frequency of M. As a consequence we derive resonance statements for closed geodesics on spheres; in particular either all homology on  of sufficiently high degreee lies hanging on closed geodesics of mean frequency (length/average index) , or there is a sequence of infinitely many closed geodesics whose mean frequencies converge to . The proof uses the ChasSullivan product and results of Goresky-Hingston [7].

No abstract uploaded!