Generalization of Johnson's and Talwar's scheduling rules in two-machine stochastic flow shops

The paper deals with the classical problem of minimizing the makespan in a two-machine flow shop. When the job processing times are deterministic, the optimal job sequence can be determined by applying Johnson's rule. When they are independent and exponential random variables, Talwar's rule yields a job sequence that minimizes the makespan stochastically. Assuming that the random job processing times are independent and Gompertz distributed, we propose a new scheduling rule that is a generalization of both Johnson's and Talwar's rules. We prove that our rule yields a job sequence that minimizes the makespan stochastically. Extensions to m-machine proportionate stochastic flow shops, two-machine stochastic job shops, and stochastic assembly systems are indicated.     

Johnson’s problem with stochastic processing times and optimal service level

Theoretical results about Johnson’s problem with stochastic processing times are few. In general, just finding the expected makespan of a given sequence is already difficult, even for discrete processing time distributions. Furthermore, to obtain optimal service level we need to compute the entire distribution of the makespan. Therefore the use of heuristics and simulation is justified. We show that pursuing the minimal expected makespan by two heuristics is empirically effective for obtaining excellent overall distributions. The first is to use Johnson’s rule on the means. The second is based on pair-switching and converges to some known stochastically optimal solutions when they apply. We show that the first heuristic is asymptotically optimal under mild conditions. We also investigate the effect of sequencing on the makespan variance.     

Single-machine and two-machine flowshop scheduling with general learning functions

We show that the O(n log n) (where n is the number of jobs) shortest processing time (SPT) sequence is optimal for the single-machine makespan and total completion time minimization problems when learning is expressed as a function of the sum of the processing times of the already processed jobs. We then show that the two-machine flowshop makespan and total completion time minimization problems are solvable by the SPT sequencing rule when the job processing times are ordered and job-position-based learning is in effect. Finally, we show that when the more specialized proportional job processing times are in place, then our flowshop results apply also in the more general sum-of-job-processing-times-based learning environment.     

Single machine scheduling with general time-dependent deterioration, position-dependent learning and past-sequence-dependent setup times

The paper deals with single machine scheduling problems with setup time considerations where the actual processing time of a job is not only a non-decreasing function of the total normal processing times of the jobs already processed, but also a non-increasing function of the job’s position in the sequence. The setup times are proportional to the length of the already processed jobs, i.e., the setup times are past-sequence-dependent (p-s-d). We consider the following objective functions: the makespan, the total completion time, the sum of the δth (δ ≥ 0) power of job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the δ th (δ ≥ 0) power of job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

Johnson’s rule,composite jobs and the relocation problem

Two-machine flowshop scheduling to minimize makespan is one of the most well-known classical scheduling problems. Johnson’s rule for solving this problem has been widely cited in the literature. We introduce in this paper the concept of composite job, which is an artificially constructed job with processing times such that it will incur the same amount of idle time on the second machine as that incurred by a chain of jobs in a given processing sequence. This concept due to Kurisu first appeared in 1976 to deal with the two-machine flowshop scheduling problem involving precedence constraints among the jobs. We show that this concept can be applied to reduce the computational time to solve some related scheduling problems. We also establish a link between solving the two-machine flowshop makespan minimization problem using Johnson’s rule and the relocation problem introduced by Kaplan. We present an intuitive interpretation of Johnson’s rule in the context of the relocation problem.     

Some single-machine scheduling with both learning and deterioration effects

In this paper we consider the single-machine scheduling problems with both learning and deterioration effects. By the effects of learning and deterioration, we mean that job processing times are defined by functions of their starting times and positions in the sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, single-machine makespan minimization problem and the sum of the θth power of job completion times minimization problem remain polynomially solvable, respectively. But for the following objective functions: the weighted sum of completion times and the maximum lateness, this paper proves that the WSPT rule and the EDD rule can construct the optimal sequence under some special cases, respectively.     

Single machine scheduling with a time-dependent learning effect and deteriorating jobs

The paper deals with the single machine scheduling problems with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the processing time of a job is defined by function of its starting time and total normal processing time of jobs in front of it in the sequence. It is shown that even with the introduction of a time-dependent learning effect and deteriorating jobs to job processing times, the single machine makespan minimization problem remain polynomially solvable. But for the total completion time minimization problem, the classical shortest processing time first rule or largest processing time first rule cannot give an optimal solution.     

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.     

A polynomial time heuristic for the two-machine flowshop scheduling problem with setup times and random processing times

The two-machine flowshop scheduling problem to minimize makespan is addressed. Jobs have random processing times which are bounded within certain intervals. The distributions of job processing times are not known. This problem has been addressed in the literature with the assumption that setup times are included in processing times or are zero. In this paper, we relax this assumption and treat setup times as separate from processing times. We propose a polynomial time heuristic algorithm. Both Johnson algorithm and Yoshida and Hitomi algorithm, both of which developed for the deterministic problem, are special cases of the proposed algorithm. The heuristic algorithm uses a weighted average of lower and upper bounds for processing times. For different weights, the results of the proposed algorithm are compared based on randomly generated data. The computational analysis has shown that the proposed algorithm, with equal weights given to the lower and upper bounds, performs considerably well with an overall average error of 0.36%. The analysis has also shown that the proposed algorithm can safely be used regardless of processing time distributions and the range between lower and upper bounds.     

Scheduling jobs with position-dependent processing times

The paper is devoted to some single machine scheduling problems, where job processing times are defined by functions dependent on their positions in the sequence. It is assumed that each job is available for processing at its ready time. We prove some properties of the special cases of the problems for the following optimization criteria: makespan, total completion time and total weighted completion time. We prove strong NP-hardness of the makespan minimization problem for two different models of job processing time. The reductions are done from the well-known 3-Partition Problem. In order to solve the makespan minimization problems, we suggest the Earliest Ready Date algorithms, for which the worst-case ratios are calculated. We also prove that the makespan minimization problem with job ready times is equivalent to the maximum lateness minimization problem.     

带有退化效应和序列相关运输时间的排序问题

考虑带有退化效应和序列相关运输时间的单机排序问题. 工件的加工时间是其开工时间的简单线性增加函数. 当机器单个加工工件时, 极小化最大完工时间、(加权)总完工时间和总延迟问题被证明是多项式可解的, EDD序对于极小化最大延迟问题不是最优排序, 另外, 就交货期和退化率一致情形给出了一最优算法. 当机器可分批加工工件时, 分别就极小化最大完工时间和加权总完工时间问题提出了多项式时间最优算法.     

Single machine scheduling with a general exponential learning effect

In this paper we consider the scheduling problem with a general exponential learning effect and past-sequence-dependent (p-s-d) setup times. By the general exponential learning effect, we mean that the processing time of a job is defined by an exponent function of the total weighted normal processing time of the already processed jobs and its position in a sequence, where the weight is a position-dependent weight. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the δ ? 0th power of completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

Tabu search for discrete–continuous scheduling problems with heuristic continuous resource allocation

Problems of scheduling non-preemptable, independent jobs on parallel identical machines under an additional continuous renewable resource to minimize the makespan are considered. Each job simultaneously requires for its processing a machine and an amount (unknown in advance) of the continuous resource. The processing rate of a job depends on the amount of the resource allotted to this job at a time. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation that minimize the makespan. A heuristic procedure for allocating the continuous resource is used. The tabu search metaheuristic to solve the considered problem is presented. The results produced by tabu search are compared with optimal solutions for small instances, as well as with the results generated by simple search methods – multi-start iterative improvement and random sampling for larger instances.     

Learning effect and deteriorating jobs in the single machine scheduling problems

This paper studies the single machine scheduling problems with learning effect and deteriorating jobs simultaneously. In this model, the processing times of jobs are defined as functions of their starting times and positions in a sequence. It is shown that even with the introduction of learning effect and deteriorating jobs to job processing times, the makespan, the total completion time and the sum of the k$k$th power of completion times minimization problems remain polynomially solvable, respectively. But for the following objective functions: the total weighted completion time and the maximum lateness, this paper proves that the shortest weighted processing time first (WSPT) rule and the earliest due-date first (EDD) rule can construct the optimal sequence under some special cases, respectively.     

On the optimality of static policy in stochastic open shop

Consider n jobs and two machines. Each job has to be processed on both machines. The order in which it is dome is immaterial. However, the decision maker has to decide in advance which jobs will be processes first on machine 1 (2). We assume that processing times on each machine are identically exponentially distributed random variables. We prove that assigning equal number of jobs to be first processed by machine 1 (2) stochastically minimizes the makespan.     

Some single-machine scheduling problems with actual time and position dependent learning effects

In this paper we study some single-machine scheduling problems with learning effects where the actual processing time of a job serves as a function of the total actual processing times of the jobs already processed and of its scheduled position. We show by examples that the optimal schedules for the classical version of problems are not optimal under this actual time and position dependent learning effect model for the following objectives: makespan, sum of kth power of the completion times, total weighted completion times, maximum lateness and number of tardy jobs. But under certain conditions, we show that the shortest processing time (SPT) rule, the weighted shortest processing time (WSPT) rule, the earliest due date (EDD) rule and the modified Moore’s Algorithm can also construct an optimal schedule for the problem of minimizing these objective functions, respectively.     

Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect

In this paper we consider the single machine scheduling problems with exponential sum-of-logarithm-processing-times based learning effect. By the exponential sum-of-logarithm-processing-times based learning effect, we mean that the processing time of a job is defined by an exponent function of the sum of the logarithm of the processing times of the jobs already processed. We consider the following objective functions: the makespan, the total completion time, the sum of the quadratic job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

Two-Stage Production Scheduling with Separated Set-up Times and Stochastic Breakdowns

The problem of scheduling a two-machine flowshop, where set-up times are considered as separate from processing times and machines suffer random breakdowns, is addressed with respect to the makespan objective. A dominance relation for minimizing makespan with probability 1 is established. Furthermore, it is shown that Yoshida and Hitomi's algorithm for the deterministic problem stochastically minimizes makespan when random breakdowns are present.     

Trapezoidal type inequalities for n-time differentiable functions

In this paper we consider the flow shop scheduling problems with the effects of learning and deterioration. In this model the processing times of a job is defined as a function of its starting time and position in a sequence. The scheduling objective functions are makespan and total completion time. We prove that even with the introduction of learning effect and deteriorating jobs to job processing times, some special flow shop scheduling problems remain polynomially solvable.     

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.