Flow shop scheduling algorithms for minimizing the completion time variance and the sum of squares of completion time deviations from a common due date

We consider two problems of m-machine flow shop scheduling in this paper: one, with the objective of minimizing the variance of completion times of jobs, and the other with the objective of minimizing the sum of squares of deviations of job completion times from a common due date. Lower bounds on the sum of squares of deviations of job completion times from the mean completion time of jobs for a given partial sequence are first presented. Using these lower bounds, a branch and bound algorithm based on breadth-first search procedure for scheduling n jobs on m-machines with the objective of minimizing completion time variance (CTV) is developed to obtain the best permutation sequence. We also present two lower bounds and thereafter, a branch and bound algorithm with the objective of minimizing the sum of squares of deviations of job completion times from a given common due date (called the MSD problem). The computational experience with the working of the two proposed branch and bound algorithms is also reported. Two heuristics, one for each of the two problems, are developed. The computational experience on the evaluation of the heuristics is discussed.     

Single-machine scheduling problems with past-sequence-dependent setup times

This paper studies single-machine scheduling problems with setup times which are proportionate to the length of the already scheduled jobs, that is, with past-sequence-dependent or p-s-d setup times. The following objective functions are considered: the maximum completion time (makespan), the total completion time, the total absolute differences in completion times and a bicriteria combination of the last two objective functions. It is shown that the standard single-machine scheduling problem with p-s-d setup times and any of the above objective functions can be solved in O(nlog n) time (where n is the number of jobs) by a sorting procedure. It is also shown that all of our results extend to a “learning” environment in which the p-s-d setup times are no longer linear functions of the already elapsed processing time due to learning effects.     

A cumulative not-first/not-last filtering algorithm in O(n 2log(n))

In cumulative and disjunctive constraint-based scheduling, the resource constraint is enforced by several filtering rules. Among these rules, we have (extended) edge-finding and not-first/not-last rules. The not-first/not-last rule detects tasks that cannot run first/last relatively to a set of tasks and prunes their time bounds. In this paper, it is presented a sound O (n ² log n) algorithm for the cumulative not-first/not-last rule where n is the number of tasks. This algorithm reaches the same fix point as previous not-first/not-last algorithms, although it may take additional iterations to do so. The worst case complexity of this new algorithm for the maximal adjustment is the same as our previous complete O (n ²|H| log n) not-first/not-last algorithm [7] where |H| is the maximum between the number of distinct earliest completion and latest start times of tasks. But, experimental results on benchmarks from the Project Scheduling Problem Library (PSPLib) and the Baptiste and Le Pape data set (BL) suggest that the new not-first/not-last algorithm has a substantially reduced runtime. Furthermore, the results demonstrate that in practice the new algorithm rarely requires more propagations than previous not-first/not-last algorithms.     

An improved branch and bound algorithm for single machine scheduling with deadlines to minimize total weighted completion time

We consider a scheduling problem in which n jobs with distinct deadlines are to be scheduled on a single machine. The objective is to find a feasible job sequence that minimizes the total weighted completion time. We present an efficient branch-and-bound algorithm that fully exploits the principle of optimality. Favorable numerical results are also reported on an extensive set of problem instances of 20-120 jobs.     

Parallel-machine scheduling with non-simultaneous machine available time

We consider a problem of scheduling n independent jobs on m parallel identical machines. The jobs are available at time zero, but the machines may not be available simultaneously at time zero. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time and total absolute differences in completion times; minimizing a cost function containing total waiting time and total absolute differences in waiting times. In this paper, we present polynomial time algorithm to solve this problem.     

On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times

We consider the single machine, serial batching, total completion time scheduling problem with precedence constraints, release dates and identical processing times in this paper. The complexity of this problem is reported as open in the literature. We provide an O(n⁵) time algorithm to solve this problem.     

Single-Machine Scheduling with Release Times and Tails

We study the problem of scheduling jobs with release times and tails on a single machine with the objective to minimize the makespan. This problem is strongly NP-hard, however it is known to be polynomially solvable if all jobs have equal processing time P. We generalize this result and suggest an O(n ² log nlog P) algorithm for the case when the processing times of some jobs are restricted to either P or 2P.     

Single machine scheduling problems with controllable processing times and total absolute differences penalties

In this paper, we consider single machine scheduling problem in which job processing times are controllable variables with linear costs. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time, total absolute differences in completion times and total compression cost; minimizing a cost function containing total waiting time, total absolute differences in waiting times and total compression cost. The problem is modelled as an assignment problem, and thus can be solved with the well-known algorithms. For the case where all the jobs have a common difference between normal and crash processing time and an equal unit compression penalty, we present an O(n log n) algorithm to obtain the optimal solution.     

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

This paper considers single machine scheduling with past-sequence-dependent (psd) delivery times, in which the processing time of a job depends on its position in a sequence. We provide a unified model for solving single machine scheduling problems with psd delivery times. We first show how this unified model can be useful in solving scheduling problems with due date assignment considerations. We analyze the problem with four different due date assignment methods, the objective function includes costs for earliness, tardiness and due date assignment. We then consider scheduling problems which do not involve due date assignment decisions. The objective function is to minimize makespan, total completion time and total absolute variation in completion times. We show that each of the problems can be reduced to a special case of our unified model and solved in O(n ³) time. In addition, we also show that each of the problems can be solved in O(nlogn) time for the spacial case with job-independent positional function.     

Scheduling with target start times

We address the single-machine problem of scheduling n independent jobs subject to target start times. Target start times are essentially release times that may be violated at a certain cost. The objective is to minimize a bicriteria objective function that is composed of total completion time and maximum promptness, which measures the observance of these target start times. We show that in case of a linear objective function the problem is solvable in O(n⁴) time if preemption is allowed or if total completion time outweighs maximum promptness.     

Parallel machine scheduling with machine availability and eligibility constraints

In this paper we consider the problem of scheduling n independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the makespan. Each machine is not continuously available at all times and each job can only be processed on specified machines. A network flow approach is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time binary search algorithm to either verify the infeasibility of the problem or solve it optimally if a feasible schedule exists.     

Scheduling with controllable release dates and processing times: Total completion time minimization

The single machine scheduling problem with two types of controllable parameters, job processing times and release dates, is studied. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amounts. The objective is to minimize the sum of the total completion time of the jobs and the total compression cost. For the problem with equal release date compression costs we construct a reduction to the assignment problem. We demonstrate that if in addition the jobs have equal processing time compression costs, then it can be solved in O(n²) time. The solution algorithm can be considered as a generalization of the algorithm that minimizes the makespan and total compression cost. The generalized version of the algorithm is also applicable to the problem with parallel machines and to a range of due-date scheduling problems with controllable processing times.     

Flowshop scheduling problem to minimize total completion time with random and bounded processing times

The flowshop scheduling problems with n jobs processed on two or three machines, and with two jobs processed on k machines are addressed where jobs have random and bounded processing times. The probability distributions of random processing times are unknown, and only the lower and upper bounds of processing times are given before scheduling. In such cases, there may not exist a unique schedule that remains optimal for all feasible realizations of the processing times, and therefore, a set of schedules has to be considered which dominates all other schedules for the given criterion. We obtain sufficient conditions when transposition of two jobs minimizes total completion time for the cases of two and three machines. The geometrical approach is utilized for flowshop problem with two jobs and k machines.     

Scheduling Parts in a Combined Production-transportation Work Cell

This paper is concerned with a combined production-transportation scheduling problem. The problem comprises a simple, two-machine, automated manufacturing cell, which either stands alone or is a subunit of a complete flexible manufacturing system. The cell consists of two machines in series with a dedicated part-handling device such as a crane or robotic arm for transferring parts from the first machine to the second. The loading of a new piece on the first machine and the ejection of a finished piece from the second machine are performed by dedicated automated mechanisms. The introduction of parts into the system is done n at a time, whereby the parts are reshuffled into a sequence that minimizes completion time. All processing and transfer times are considered deterministic—a reasonable assumption for a cell comprising a robotic transfer device and two CNC machining units. What complicates the problem is the assumption of a non-negligible time for the transfer device to return (empty) from the second machine to the first. The operation is a generalization of a two-machine flowshop problem, and is formulated as a specially structured, asymmetric travelling salesman problem. An approximate polynomial time 0(n log n) algorithm is proffered. The procedure incorporates a lower bound using the Gilmore–Gomory algorithm for the no-wait, two-machine flowshop problem.     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （Part Ⅱ Heuristics for the General Case）

A single machine scheduling problem with controllable processing times and compression costs is considered. The objective is to find an optimal sequence to minimize the cost ofcompletion times and the cost of compression. The complexity of this problem is still unknown.In Part Ⅱ of this paper,the authors have considered a special case where the compression timesand the compression costs are equal among all jobs. Such a problem appears polynomiafiy solvable by developing an O(n^2) algorithm. In this part(Part Ⅱ ),a general case where the controllable processing times and the compression costs are not equal is discussed. Authors proposehere two heuristics with the first based on some previous work and the second based on the algorithm developed in Part Ⅱ . Computational results are presented to show the efficiency and therobustness of these heuristics.     

A note on scheduling to meet two min-sum objectives

We consider a single machine scheduling problem with two min-sum objective functions: the sum of completion times and the sum of weighted completion times. We propose a simple polynomial time (1+(1/γ),1+γ)-approximation algorithm, and show that for γ>1, there is no (x,y)-approximation with 1<x<1+(1/γ) and 1<y<1+(γ-1)/(2+γ).     

Heuristic constructive algorithms for open shop scheduling to minimize mean flow time

In this paper, we consider the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. For this strongly NP-hard problem, we develop and discuss different constructive heuristic algorithms. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The quality of the solutions is evaluated by a lower bound for the corresponding preemptive open shop problem and by an alternative estimate of mean flow time. We observe that the recommendation of an appropriate constructive algorithm strongly depends on the ratio n/m.     

Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan

This paper studies the bicriteria problem of scheduling n jobs on a serial-batching machine to minimize maximum cost and makespan simultaneously. A serial-batching machine is a machine that can handle up to b jobs in a batch and jobs in a batch start and complete respectively at the same time and the processing time of a batch is equal to the sum of the processing times of jobs in the batch. When a new batch starts, a constant setup time s occurs. We confine ourselves to the unbounded model, where b ≥ n. We present a polynomial-time algorithm for finding all Pareto optimal solutions of this bicriteria scheduling problem.     

Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint

We study the problem of scheduling n non-preemptable jobs on a single machine which is not available for processing during a given time period. The objective is to minimize the sum of the job completion times. The best known approximation algorithm for this NP-hard problem has a relative worst-case error bound of 17.6%. We present a parametric O(nlog n)-algorithm H with which better worst-case error bounds can be obtained. The best error bound calculated for the algorithm in the paper is 7.4%. In a computational experiment, we test the algorithm with the performance guarantee set to 10.2%. It turns out that randomly generated instances with up to 1000 jobs can be solved with a mean (maximum) error of 0.31% (3.18%) and a mean (maximum) computation time of 0.8 (9.7) seconds.