Resource-constrained job scheduling with recyclable resources

In resource-constrained project scheduling problems, resources are typically classified as being either renewable, non-renewable, or doubly-constrained. A new resource classification, recyclable, is introduced. Notation and a generalized problem formulation are developed for resource-constrained job scheduling problems where resources are recyclable. This foundation is then used for studying the single-machine scheduling problem with tooling constraints. For a given set of jobs, the problem is to find the job sequence, tool type quantities, and tool recycling schedule such that the sum of job completion times and quantity of tools allocated are both minimized. Two solution approaches are developed, and examples are used to compare and contrast the approaches. The results indicate that the ‘traditional’ job scheduling approach (i.e. schedule jobs first, then tools) can lead to sub-optimal solutions. Furthermore, by scheduling jobs and tools simultaneously, it may be possible to attain a given level of performance with fewer tools.     

Single-machine scheduling with deteriorating functions for job processing times

In many realistic scheduling settings a job processed later consumes more time than when it is processed earlier – this phenomenon is known as scheduling with deteriorating jobs. In the literature on deteriorating job scheduling problems, majority of the research assumed that the actual job processing time of a job is a function of its starting time. In this paper we consider a new deterioration model where the actual job processing time of a job is a function of the processing times of the jobs already processed. We show that the single-machine scheduling problems to minimize the makespan and total completion time remain polynomially solvable under the proposed model. In addition, we prove that the problems to minimize the total weighted completion time, maximum lateness, and maximum tardiness are polynomially solvable under certain agreeable conditions.     

Buyback problem with discrete concave valuation functions

We discuss an online discrete optimization problem called the buyback problem. In the literature of the buyback problem, the valuation function representing the total value of selected elements is given by a linear function. In this paper, we consider a generalization of the buyback problem using nonlinear valuation functions. We propose an online algorithm for the problem with discrete concave valuation functions, and show that it achieves the tight competitive ratio, i.e., the competitive ratio of the proposed algorithm is equal to the known lower bound for the problem.     

Integrals of logarithmically concave functions

In this note we consider integrals of the form

Single-machine scheduling with learning functions

In this study we consider the single-machine scheduling problems with a sum of-processing-times-based learning effect. The sum of-processing-times-based learning effect of a job is assumed to be a function of the sum of the normal processing time of the already processed jobs. The objective is to minimize one of two regular objective functions, namely the weighted sum of completion times and the maximum lateness. We use the weighted shortest processing time (WSPT) rule and the earliest due date (EDD) rule as heuristics for the general cases and analyze their worst-case error bounds. We also provide computational results to evaluate the performance of the heuristics.     

Global solutions of mathematical programs with intrinsically concave functions

An implicit enumeration technique for solving a certain type of nonconvex program is described. The method can be used for solving signomial programs with constraint functions defined by sums of quasiconcave functions and other types of programs with constraint functions called intrinsically concave functions. A signomial-type example is solved by this method. The algorithm is described together with a convergence proof. No computational results are available at present.     

Linearly constrained global minimization of functions with concave minorants

In this note, we show how a recent approach for solving linearly constrained multivariate Lipschitz optimization problems and corresponding systems of inequalities can be generalized to solve optimization problems where the objective function is only assumed to possess a concave minorant at each point. This class of functions includes not only Lipschitz functions and some generalizations, such as certain -convex functions and Hölder functions with exponent greater than one, but also all functions which can be expressed as differences of two convex functions (d.c. functions). Thus, in particular, a new approach is obtained for the important problem of minimizing a d.c. function over a polytope.     

Optimization for products of concave functions

Ifh denotes the product of finitely many concave non-negative functions on a compact interval [a, b], then it is shown that there exist pointsα andβ witha≤α≤β≤b such thath is strictly increasing on [α, α), constant on (α, β), and strictly decreasing on (β, b]. This structure theorem leads to an extension of several classical optimization results for concave functions on convex sets to the case of products of concave functions.     

Strongly concave functions on root systems

Let F be a local complete field with discrete valuation, and let G be the group of F-points of a quasisplit group over F. Let ℬ be the Bruhat-Tits building of G and let A be an apartment of ℬ; we establish a link between bounded closed subsets of A and a special kind of functions on the relative root system Φ of G, which will be called strongly concave functions. This paper is devoted to the study of such functions.     

A general two-sided matching market with discrete concave utility functions

In the theory of two-sided matching markets there are two standard models: (i) the marriage model due to Gale and Shapley and (ii) the assignment model due to Shapley and Shubik. Recently, Eriksson and Karlander introduced a hybrid model, which was further generalized by Sotomayor. In this paper, we propose a common generalization of these models by utilizing the framework of discrete convex analysis introduced by Murota, and verify the existence of a pairwise-stable outcome in our general model.     

Single-machine scheduling with time-and-resource-dependent processing times

We consider single-machine scheduling problems in which the processing time of a job is a function of its starting time and its resource allocation. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. We concentrate on two goals separately, namely, minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. We show that the problems remain polynomially solvable under the proposed model.     

Inequalities involving integrals of polar-conjugate concave functions

An inequality of K. Mahler, together with its case of equality, due to M. Meyer, are extended to integrals of powers of polar-conjugate concave functions. An application to estimation of the volume-product of certain convex bodies is given.     

Railway scheduling reduces the expected project makespan over roadrunner scheduling in a multi-mode project scheduling environment

The Critical Chain Scheduling and Buffer Management (CC/BM) methodology, proposed by Goldratt (Critical chain, 1997), introduced the concepts of feeding buffers, project buffers and resource buffers as well as the roadrunner mentality. This last concept, in which activities are started as soon as possible, was introduced in order to speed up projects by taking advantage of predecessors finishing early. Later on, the railway scheduling concept of never starting activities earlier than planned was introduced as a way to increase the stability of the project, typically at the cost of an increase in the expected project makespan. In this paper, we will indicate a realistic situation in which railway scheduling improves both the stability and the expected project makespan over roadrunner scheduling.     

Online scheduling with general machine cost functions

For most scheduling problems the set of machines is fixed initially and remains unchanged for the duration of the problem. Recently online scheduling problems have been investigated with the modification that initially the algorithm possesses no machines, but that at any point additional machines may be purchased. In all of these models the assumption has been made that each machine has unit cost. In this paper we consider the problem with general machine cost functions. Furthermore we also consider a more general version of the problem where the available machines have speed, the algorithm may purchase machines with speed 1 and machines with speed s. We define and analyze some algorithms for the solution of these problems and their special cases. Moreover we prove some lower bounds on the possible competitive ratios.     

Single machine scheduling with exponential learning functions

In this paper we consider the single machine scheduling problem with exponential learning functions. By the exponential learning functions, we mean that the actual job processing time is a function of the total normal processing times of the jobs already processed. We prove that the shortest processing time (SPT) rule is optimal for the total lateness minimization problem. For the following three objective functions, the total weighted completion time, the discounted total weighted completion time, the maximum lateness, we present heuristic algorithms according to the corresponding problems without exponential learning functions. We also analyse the worst-case bound of our heuristic algorithms. It also shows that the problems of minimizing the total tardiness and discounted total weighted completion time are polynomially solvable under some agreeable conditions on the problem parameters.     

Single-machine scheduling with time window-dependent processing times

In the one-machine scheduling problems analysed in this paper, the processing time of a job depends on the time at which the job is started. More precisely, the horizon is divided into time windows and with each one a coefficient is associated that is used to determine the actual processing time of a job starting in it. Two models are introduced, and one of them has direct connections with models considered in previous papers on scheduling problems with time-dependent processing times. Various computational complexity results are presented for the makespan criterion, which show that the problem is NP-hard, even with two time windows. Solving procedures are also proposed for some special cases.