Some single-machine scheduling with sum-of-processing-time-based and job-position-based processing times

The single-machine scheduling problems with position and sum-of-processing-time based processing times are considered. The actual processing time of a job is defined by function of its scheduled position and total normal processing time of jobs in front of it in the sequence. We provide optimal solutions in polynomial time for some special cases of the makespan minimization and the total completion time minimization. We also show that an optimal schedule to be a V-shaped schedule in terms of the normal processing times of jobs for the total completion time minimization problem and the makespan minimization problem.     

Scheduling with controllable release dates and processing times: Makespan minimization

The paper deals with the single-machine scheduling problem in which job processing times as well as release dates are controllable parameters and they may vary within given intervals. While all release dates have the same boundary values, the processing time intervals are arbitrary. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amount. The objective is to minimize the makespan together with the total compression cost. We construct a reduction to the assignment problem for the case of equal release date compression costs and develop an O(n²) algorithm for the case of equal release date compression costs and equal processing time compression costs. For the bicriteria version of the latter problem with agreeable processing times, we suggest an O(n²) algorithm that constructs the breakpoints of the efficient frontier.     

Makespan minimization in online scheduling with machine eligibility

In this paper we provide a survey of online scheduling in parallel machine environments with machine eligibility constraints and the makespan as objective function. We first give a brief overview of the different parallel machine environments and then survey the various types of machine eligibility constraints, including tree-hierarchical processing sets, Grade of Service processing sets, interval processing sets, and nested processing sets. We furthermore describe the relationships between the various different types of processing sets. We proceed with describing two basic online scheduling paradigms, namely online over list and online over time. For each one of the two paradigms we survey all the results that have been recorded in the literature with regard to each type of machine eligibility constraints. We obtain also several extensions in various directions. In the concluding section we describe the most important open problems in this particular area.     

Makespan minimization in online scheduling with machine eligibility

In this paper we provide a survey of online scheduling in parallel machine environments with machine eligibility constraints and the makespan as objective function. We first give a brief overview of the different parallel machine environments and then survey the various types of machine eligibility constraints, including tree-hierarchical processing sets, Grade of Service processing sets, interval processing sets, and nested processing sets. We furthermore describe the relationships between the various different types of processing sets. We proceed with describing two basic online scheduling paradigms, namely online over list and online over time. For each one of the two paradigms we survey all the results that have been recorded in the literature with regard to each type of machine eligibility constraints. We obtain also several extensions in various directions. In the concluding section we describe the most important open problems in this particular area.     

A note on single-machine scheduling with decreasing time-dependent job processing times

In this note we consider some single-machine scheduling problems with decreasing time-dependent job processing times. Decreasing time-dependent job processing times means that its processing time is a non-increasing function of its execution start time. We present polynomial solutions for the sum of squared completion times minimization problem, and the sum of earliness penalties minimization problem subject to no tardy jobs, respectively. We also study two resource constrained scheduling problems under the same decreasing time-dependent job processing times model and present algorithms to find their optimal solutions.     

The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times

We study the earliness-tardiness scheduling problem on a single machine with due date assignment and controllable processing times. We analyze the problem with three different due date assignment methods and two different processing time functions. For each combination of these, we provide a polynomial-time algorithm to find the optimal job sequence, due date values and resource allocation minimizing an objective function which includes earliness, tardiness, due date assignment, makespan and total resource consumption costs.     

Makespan minimization for parallel machines scheduling with multiple availability constraints

The problem of makespan minimization for parallel machines scheduling with multiple planned nonavailability periods in the case of resumable jobs is considered. In the current state of the literature, there is a limited number of models and algorithms dealing with this problem and only for very small problem size, and nonavailability limited to some machines. The problem is first formulated as a mixed integer linear programming model and optimally solved using CPLEX for small to moderately large size problems with multiple availability constraints on all machines. An implicit enumeration algorithm using the lexicographic order is then designed to solve large-scale problems. Numerical results are obtained for several experiments and they show the validity and performance improvements procured by both the MILP model and the new enumeration algorithm.     

Bi-criterion single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times

This paper addresses single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times. Due-window assignment with common flow allowances means that each job has a job-dependent due window, the start time and finish time of which are equal to its actual processing time plus individual job-independent parameters shared by all the jobs, respectively. The processing time of each job can be controlled by extra resource allocation as a linear function of the amount of a common continuously divisible resource allocated to the job. Two criteria are considered, where one criterion is an integrated cost consisting of job earliness, weighted number of tardy jobs, and due-window assignment cost, while the other criterion is the resource consumption cost. Four different models are considered for treating the two criteria. It is shown that the problem under the model where the two criteria are integrated into a single criterion is polynomially solvable, while the problems under the other three models are all NP-hard and an optimal solution procedure is developed for them. Two polynomially solvable cases are also identified and investigated. Finally, numerical studies with randomly generated instances are conducted to assess the performance of the proposed algorithms.     

A unified analysis for the single-machine scheduling problem with controllable and non-controllable variable job processing times

We present a unified analysis for single-machine scheduling problems in which the actual job processing times are controlled by either a linear or a convex resource allocation function and also vary concurrently depending on either the job’s position in the sequence and/or on the total processing time of the already processed jobs. We show that the problem is solvable in O(nlogn)$O(n\log n)$ time by using a weight-matching approach when a convex resource allocation function is in effect. In the case of a linear resource allocation function, we show that the problem can be solved in O(n³)$O(n^3)$ time by using an assignment formulation. Our approach generalizes the solution approach for the corresponding problems with controllable job processing times to incorporate the variability of the job processing times stemming from either the job’s position in the sequence and/or the total processing time of the already processed jobs.     

A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times

We consider a scheduling problem in which the processing time of each job deteriorates, i.e. it increases as time passes after the release date of the job. We present a dynamic programming algorithm coupled with upper bounding and lower bounding techniques to compute exact solutions. We report on problem instances of different size and we analyze the dependence between the ranges to which the data belong and the computing time.     

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.     

Makespan minimization in machine dominated flowshop

In a flowshop scheduling problem, a set of jobs is processed by a set of machines. The jobs follow the same sequence in all machines. We study the flowshop scheduling problem under a new case of machine dominance that is often found in the manufacturing of computers and electronic devices. We provide a formula for makespan value for a given sequence, show that the makespan value depends only on certain jobs in the sequence, and present an algorithm that finds a sequence with minimum makespan. Numerical examples of the solution approaches are provided.     

A multi-objective tabu search for a single-machine scheduling problem with sequence-dependent setup times

An m-objective tabu search algorithm for sequencing of n jobs on a single machine with sequence-dependent setup times is proposed. The algorithm produces a solution set that is reflective of the objectives’ weights and close to the best observed values of the objectives. We also formulate a mixed integer linear program to obtain the optimal solution of a three-objective problem. Numerical examples are used to study the behavior of the proposed m-objective tabu search algorithm and compare its solutions with those of the mixed integer linear program.     

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.     

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.     

A survey of scheduling with controllable processing times

In classical deterministic scheduling problems, the job processing times are assumed to be constant parameters. In many practical cases, however, processing times are controllable by allocating a resource (that may be continuous or discrete) to the job operations. In such cases, each processing time is a decision variable to be determined by the scheduler, who can take advantage of this flexibility to improve system performance. Since scheduling problems with controllable processing times are very interesting both from the practical and theoretical point of view, they have received a lot of attention from researchers over the last 25 years. This paper aims to give a unified framework for scheduling with controllable processing times by providing an up-to-date survey of the results in the field.     

Single machine scheduling with randomly compressible processing times

This work is concerned with single machine scheduling with random compression of processing times. The objective is to find the optimal sequence to minimize the cost based on earliness, tardiness and compression. The analysis is carried out under a common due date. Both absolute derivation cost and squared derivation cost are considered. For both constrained problems and unconstrained problems, it is shown that an optimal schedule must be V-shaped. Remarks on common slack model is also provided.     

Single-machine scheduling problems with past-sequence-dependent delivery times and position-dependent processing times

This paper considers single-machine scheduling problems with job delivery times where the actual job processing time of a job is defined by a function dependent on its position in a schedule. We assume that the job delivery time is proportional to the job waiting time. We investigate the minimization problems of the sum of earliness, tardiness, and due-window-related cost, the total absolute differences in completion times, and the total absolute differences in waiting times on a single-machine setting. The polynomial time algorithms are proposed to optimally solve the above objective functions. We also investigate some special cases of the problem under study and show that they can be optimally solved by lower order algorithms.     

Flow shop scheduling jobs with position-dependent processing times

The paper is devoted to some flow shop scheduling problems, where job processing times are defined by functions dependent on their positions in the schedule. An example is constructed to show that the classical Johnson's rule is not the optimal solution for two different models of the two-machine flow shop scheduling to minimize makespan. In order to solve the makespan minimization problem in the two-machine flow shop scheduling, we suggest Johnson's rule as a heuristic algorithm, for which the worst-case bound is calculated. We find polynomial time solutions to some special cases of the considered problems for the following optimization criteria: the weighted sum of completion times and maximum lateness. Some furthermore extensions of the problems are also shown.     

Single machine scheduling with resource dependent release times and processing times

We consider the single machine scheduling problem with resource dependent release times and processing times, in which both the release times and processing times are strictly linear decreasing functions of the amount of resources consumed. The objective is to minimize the makespan plus the total resource consumption costs. We propose a heuristic algorithm for the general problem by utilizing some derived optimal properties and analyze its performance bound. For some special cases, we propose another heuristic algorithm that achieves a tighter performance bound.