Proportionate flowshops with general position-dependent processing times

Most scheduling studies assume constant (position-independent) job processing times. Most of the papers allowing position-dependent processing times consider only special cases, where the job processing times follow a specific function of the job-position. Polynomial time solutions have hardly been found for general position-dependent processing times in scheduling literature. In this note we provide one of these cases: we introduce a polynomial time solution for minimum makespan on an m-machine proportionate flowshop.     

Single-machine scheduling with learning effect and resource-dependent processing times

We consider resource allocation scheduling with learning effect in which the processing time of a job is a function of its position in a sequence 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 analyse the problem with two different processing time functions. For each combination of these, we provide a polynomial time algorithm to find the optimal job sequence and resource allocation.     

Scheduling a Single Server in a Two-machine Flow Shop

We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one machine to the other. The problem with a given job sequence is shown to be reducible to a single machine batching problem. This result enables several cases of the server scheduling problem to be solved in O(n log n) by known algorithms, namely, finding a schedule feasible with respect to a given set of deadlines, minimizing the maximum lateness and, if the job processing times are agreeable, minimizing the total completion time. Minimizing the total weighted completion time is shown to be NP-hard in the strong sense. Two pseudopolynomial dynamic programming algorithms are presented for minimizing the weighted number of late jobs. Minimizing the number of late jobs is proved to be NP-hard even if setup times are equal and there are two distinct due dates. This problem is solved in O(n ³) time when all job processing times on the first machine are equal, and it is solved in O(n ⁴) time when all processing times on the second machine are equal. Received November 20, 2001; revised October 18, 2002 Published online: January 16, 2003     

Two-machine no-wait flowshop scheduling with learning effect and convex resource-dependent processing times

Two-machine no-wait flowshop scheduling problems in which the processing time of a job is a function of its position in the sequence and its resource allocation are considered in the study. The primary objective is to find the optimal sequence of jobs and the optimal resource allocation separately. Here we propose two separate models: minimizing a cost function of makespan, total completion time, total absolute differences in completion times and total resource cost; minimizing a cost function of makespan, total waiting time, total absolute differences in waiting times and total resource cost. Since each model is strongly NP-hard, we solve both models by breaking them down to two sub-problems, the optimal resource allocation problem for any job sequence and the optimal sequence problem with its optimal resource allocation. Specially, we transform the second sub-problem into the minimum of the bipartite graph optimal matching problem (NP-hard), and solve it by using the classic KM (Kuhn–Munkres) algorithm. The solutions of the two sub-problems demonstrate that the target problems remain polynomial solvable under the proposed model.     

Minimizing the number of tardy jobs on a proportionate flowshop with general position-dependent processing times

In various real life scheduling systems job processing times vary according to the number of jobs previously processed. The vast majority of studies assume a restrictive functional form to describe job processing times. In this note, we address a scheduling problem with the most general job processing time functions. The machine setting assumed is an m-machine proportionate flowshop, and the objective function is minimum number of tardy jobs. We show that the problem can be formulated as a bottleneck assignment problem with a maximum cardinality constraint. An efficient polynomial time (O(n⁴ log n)) solution is introduced.     

An improved heuristic for parallel machine weighted flowtime scheduling with family set-up times

This paper studies the identical parallel machine scheduling problem with family set-up times and an objective of minimizing total weighted completion time (weighted flowtime). The family set-up time is incurred whenever there is a switch of processing from a job in one family to a job in another family. A heuristic is proposed in this paper for the problem. Computational results show that the proposed heuristic outperforms an existing heuristic, especially for large-sized problems, in terms of both solution quality and computation times. The improvement of solution quality is as high as 4.753% for six-machine problem and 7.822% for nine-machine problem, while the proposed heuristic runs three times faster than the existing one.     

Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs

This paper considers single machine scheduling problems with setup times and deteriorating jobs. The setup times are proportional to the length of the already processed jobs, that is, the setup times are past-sequence-dependent (p-s-d). It is assumed that the job processing times are defined by functions dependent on their starting times. The following objectives are considered: the makespan, the total completion time, and the sum of earliness, tardiness, and due-window starting time and size penalties. We propose polynomial time algorithms to solve these problems.     

Scheduling on parallel identical machines with job-rejection and position-dependent processing times

We solve scheduling problems which combine the option of job-rejection and general position-dependent processing times. The option of rejection reflects a very common scenario, where the scheduler may decide not to process a job if it is not profitable. The assumption of position-dependent processing time is a common generalization of classical settings, and contains the well-known and extensively studied special cases of “learning” and “aging”. The machine setting is parallel identical machines, and two scheduling measures are considered: total flow-time and total load. When the number of jobs is given, both problems are shown to be solved in polynomial time in the number of jobs. The special case of non-decreasing job-position processing times (“aging”) is shown to be solved much faster.     

Scheduling jobs with equal processing times and time windows on identical parallel machines

We present a linear programming approach to the problem of scheduling equal processing time jobs with release dates and deadlines on identical parallel machines. The known algorithm with complexity O(n ³log log n) of B. Simons schedules all the jobs while minimizing both the maximum completion time and the mean flow time. Our approach permits also to minimize the weighted sum of completion times and total tardiness in polynomial time for the problems without deadlines. The complexity status of these problems was open. Contract/grant sponsor: Alexander von Humboldt Foundation.     

Using quadratic programming to solve high multiplicity scheduling problems on parallel machines

We introduce and analyze several models of schedulingn different types (groups) of jobs onm parallel machines, where in each group all jobs are identical. Our main goal is to exhibit the usefulness of quadratic programming approaches to solve these classes of high multiplicity scheduling problems, with the total weighted completion time as the minimization criterion. We develop polynomial algorithms for some models, and strongly polynomial algorithms for certain special cases. In particular, the model in which the weights are job independent, as well as the generally weighted model in which processing requirements are job independent, can be formulated as an integer convex separable quadratic cost flow problem, and therefore solved in polynomial time. When we specialize further, strongly polynomial bounds are achievable. Specifically, for the weighted model with job-independent processing requirements if we restrict the weights to be machine independent (while still assuming different machine speeds), anO(mn+n logn) algorithm is developed. If it is also assumed that all the machines have the same speed, the complexity of the algorithm can be improved toO(m logm+n logn). These results can be extended to related unweighted models with variable processing requirements in which all the machines are available at time zero. The research of Frieda Granot was partially supported by Natural Sciences and Engineering Research Council of Canada Grant 5-83998. The research of Jadranka Skorin-Kapov was partially supported by National Science Foundation Grant DDM-8909206.     

Heuristics for scheduling problems with an unavailability constraint and position-dependent processing times

We study a single machine scheduling problem, where the machine is unavailable for processing for a pre-specified time period. We assume that job processing times are position-dependent. The objective functions considered are minimum makespan, minimum total completion time and minimum number of tardy jobs. All these problems are known to be NP-hard even without position-dependent processing times. For all three cases we introduce simple heuristics which are based on solving the classical assignment problem. Lower bounds, worst case analysis and asymptotic optimality are discussed. All heuristics are shown numerically to perform extremely well.     

Three scheduling problems with deteriorating jobs to minimize the total completion time

In this paper, three scheduling problems with deteriorating jobs to minimize the total completion time on a single machine are investigated. By a deteriorating job, we mean that the processing time of the job is a function of its execution start time. The three problems correspond to three different decreasing linear functions, whose increasing counterparts have been studied in the literature. Some basic properties of the three problems are proved. Based on these properties, two of the problems are solved in O(nlogn) time, where n is the number of jobs. A pseudopolynomial time algorithm is constructed to solve the third problem using dynamic programming. Finally, a comparison between the problems with job processing times being decreasing and increasing linear functions of their start times is presented, which shows that the decreasing and increasing linear models of job processing times seem to be closely related to each other.     

Note on a unified approach to the single-machine scheduling problem with a deterioration effect and convex resource allocation

In many resource allocation problems in physical or economic systems, a linear resource consumption function is commonly considered, and job processing times are assumed to be fixed parameters. However, the former assumption fails to reflect the law of diminishing returns, and the latter may be controlled by changing the allocation of resources to jobs. Motivated by these observations, we provide a unified model for solving single-machine scheduling problems in which each job's processing time is a function of its starting time and convex resource allocation. The objective is to find the optimal sequence of jobs subject to a limited resource consumption. We first show how this unified model can be useful in solving scheduling problems under due date assignment considerations. We analyze the problem with four different due date assignment methods, and our objective function includes costs for earliness, tardiness and due date assignments. We also consider scheduling problems without involving due date assignment decisions. The objective function is to minimize the makespan, total completion time, total absolute variation in completion times, and total absolute variation in waiting times. We show that several existing well-known problems can be reduced to a special case of our unified model and solved in O(nlogn) time.     

Single-machine scheduling with deteriorating jobs

In this article, we study a single-machine scheduling problem in which the processing time of a job is a nonlinear function of its basic processing time and starting time. The objectives are to minimise the makespan, the sum of weighted completion times and the sum of the kth powers of completion times. We show that the makespan minimisation problem can be solved in polynomial time. However, the total completion time and the sum of the kth powers of completion times minimisation problems can be solved in polynomial time in some cases. Besides, some useful properties are also provided for the sum of weighted completion times problem under certain conditions.     

Worst-case and numerical analysis of heuristic algorithms for flowshop scheduling problems with a time-dependent learning effect

In this paper, we investigate a time-dependent learning effect in a flowshop scheduling problem. We assume that the time-dependent learning effect of a job was a function of the total normal processing time of jobs scheduled before the job. The following objective functions are explored: the makespan, the total flowtime, the sum of weighted completion times, the sum of the kth power of completion times, and the maximum lateness. Some heuristic algorithms with worst-case analysis for the objective functions are given. Moreover, a polynomial algorithm is proposed for the special case with identical processing time on each machine and that with an increasing series of dominating machines, respectively. Finally, the computational results to evaluate the performance of the heuristics are provided.     

Flow shop scheduling to minimize makespan with decreasing time-dependent job processing times

In this study, we consider an n-job, m-machine flow shop scheduling problem with decreasing time-dependent job processing times. By the decreasing time-dependent job processing times, we mean that the processing time is a decreasing function of its execution starting time. When some dominant relationships between m − 1 machines can be satisfied, we show that the makespan minimization problem can be solved in polynomial time.     

Notes on Max Flow Time Minimization with Controllable Processing Times

In a scheduling problem with controllable processing times the job processing time can be compressed through incurring an additional cost. We consider the identical parallel machines max flow time minimization problem with controllable processing times. We address the preemptive and non-preemptive version of the problem. For the preemptive case, a linear programming formulation is presented which solves the problem optimally in polynomial time. For the non-preemptive problem it is shown that the First In First Out (FIFO) heuristic has a tight worst-case performance of 3–2/m, when jobs processing times and costs are set as in some optimal preemptive schedule. Supported by Swiss National Science Foundation project 20-63733.00/1, Resource Allocation and Scheduling in Flexible Manufacturing Systems, and by the Metaheuristics Network, grant HPRN-CT-1999-00106.     

Single-machine scheduling with trade-off between number of tardy jobs and compression cost

We consider a single-machine scheduling problem, in which the job processing times are controllable or compressible. The performance criteria are the compression cost and the number of tardy jobs. For the problem, where no tardy jobs are allowed and the objective is to minimize the total compression cost, we present a strongly polynomial time algorithm. For the problem to construct the trade-off curve between the number of tardy jobs and the maximum compression cost, we present a polynomial time algorithm. Furthermore, we extend the problem to the case of discrete controllable processing times, where the processing time of a job can only take one of several given discrete values. We show that even some special cases of the discrete controllable version with the objective of minimizing the total compression cost are NP-hard, but the general case is solvable in pseudo-polynomial time. Moreover, we present a strongly polynomial time algorithm to construct the trade-off curve between the number of tardy jobs and the maximum compression cost for the discrete controllable version. This research was supported by the Teaching and Research Award Program for Outstanding Young Teachers in Higher Education Institutions of the MOE, China, and the National Natural Science Foundation of China (10271110). The third author was supported in part by The Hong Kong Polytechnic University under a grant from the ASD in China Business Services.     

Scheduling parallel CNC machines with time/cost trade-off considerations

When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. A well-known example for such a case that this paper specifically deals with is the turning operation on a CNC machine. Manufacturing cost of a turning operation is a nonlinear convex function of its processing time. We also know that scheduling decisions are quite sensitive to the processing times. Therefore, this paper considers minimizing total manufacturing cost (_F1)$(F_1)$ and total completion time (_F2)$(F_2)$ objectives simultaneously on identical parallel CNC turning machines. Since decreasing processing time of a job increases its manufacturing cost, we cannot minimize both objectives at the same time, so the problem is to generate non-dominated solutions. We consider the problem of minimizing _F1$F_1$ subject to a given _F2$F_2$ level and give an effective formulation for the problem. For this problem, we prove some optimality properties which facilitated designing an efficient heuristic algorithm to generate approximate non-dominated solutions. Computational results show that proposed algorithm performs almost equal with the GAMS/MINOS commercial solver although it spends much less computation time.     

Scheduling a single batch processing machine with secondary resource constraints

This paper studies the problems of minimizing total completion time (ΣC_i) and makespan (Cmax) on a single batch processing machine with job families and secondary resource constraints. The motivation for this problem is the burn-in operation in the final testing stage of semiconductor manufacturing, where both oven capacity and the number of boards available may constrain scheduling decisions. Because both problems are NP-hard, integer programming formulations are developed for special cases and are then used to develop heuristics. Extensive computational experiments show that the heuristics are capable of consistently obtaining good solutions in modest CPU times.