Generalizing many well-known and natural scheduling problems, scheduling with job-specific cost functions has gained a lot of attention recently. In this setting, each job incurs a cost depending on its completion time, given by a private cost function, and one seeks to schedule the jobs to minimize the total sum of these costs. The framework captures many important scheduling objectives such as weighted flow time or weighted tardiness. Still, the general case as well as the mentioned special cases are far from being very well understood yet, even for only one machine. Aiming for better general understanding of this problem, in this paper we focus on the case of uniform job release dates on one machine for which the state of the art is a 4-approximation algorithm. This is true even for a special case that is equivalent to the covering version of the well-studied and prominent unsplittable flow on a path problem, which is interesting in its own right. For that covering problem, we present a quasi-polynomial time $$(1+\varepsilon )$$ -approximation algorithm that yields an $$(e+\varepsilon )$$ -approximation for the above scheduling problem. Moreover, for the latter we devise the best possible resource augmentation result regarding speed: a polynomial time algorithm which computes a solution with optimal cost at $$1+\varepsilon $$ speedup. Finally, we present an elegant QPTAS for the special case where the cost functions of the jobs fall into at most $$\log n$$ many classes. This algorithm allows the jobs even to have up to $$\log n$$ many distinct release dates. All proposed quasi-polynomial time algorithms require the input data to be quasi-polynomially bounded.

We consider a single-machine scheduling problem. Given some continuous, nondecreasing cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each job is determined by the cost function value at its completion time. This problem is closely related to scheduling a single machine with nonuniform processing speed. We show that for piecewise linear cost functions it is strongly NP-hard. The main contribution of this article is a tight analysis of the approximation guarantee of Smith’s rule under any convex or concave cost function. More specifically, for these wide classes of cost functions we reduce the task of determining a worst-case problem instance to a continuous optimization problem, which can be solved by standard algebraic or numerical methods. For polynomial cost functions with positive coefficients, it turns out that the tight approximation ratio can be calculated as the root of a univariate polynomial. We show that this approximation ratio is asymptotically equal to k ( k − 1)/( k + 1) , denoting by k the degree of the cost function. To overcome unrealistic worst-case instances, we also give tight bounds for the case of integral processing times that are parameterized by the maximum and total processing time.

We consider the problem of scheduling jobs on a single machine. Given a quadratic cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each job is defined as the cost function value at the job's completion time. Throughout the past decades, great effort has been made to develop fast exact algorithms for the case of quadratic costs. The efficiency of these methods heavily depends on the utilization of structural properties of optimal schedules such as order constraints, i.e., sufficient conditions for pairs of jobs to appear in a certain order. A considerable number of different kinds of such constraints have been proposed. In this work we enhance the map of known order constraints by proving an extended version of a constraint that has been conjectured by Mondal and Sen more than a decade ago. Besides proving this conjecture, our main contribution is an extensive experimental study where the influence of different kinds order constraints on the performance of exact algorithms is systematically evaluated. In addition to a best-first graph search algorithm, we test a Quadratic Integer Programming formulation that admits to add order constraints as additional linear constraints. We also evaluate the optimality gap of well known Smith's rule for different monomial cost functions. Our experiments are based on sets of problem instances that have been generated using a new method which allows us to adjust a certain degree of difficulty of the instances.