Optimal due-date assignment problem with learning effect and resource-dependent processing times

In this paper, we consider a single-machine earliness-tardiness scheduling problem with due-date assignment, in which the processing time of a job is a function of its position in a sequence and its resource allocation. The due date assignment methods studied include the common due date, and the slack due date, which reflects equal waiting time allowance for the jobs. For each combination of due date assignment method and processing time function, we provide a polynomial-time algorithm to find the optimal job sequence, due date values, and resource allocations that minimize an integrated objective function, which includes earliness, tardiness, due date assignment, and total resource consumption costs.     

Algorithms for common due-date assignment and sequencing on a single machine with sequence-dependent setup times

This paper focuses on the single machine sequencing and common due-date assignment problem for the objective of minimizing the sum of the penalties associated with earliness, tardiness and due-date assignment. Unlike the previous research articles on this class of scheduling problem, we consider sequence-dependent setup times that make the problem much more difficult. To solve the problem, a branch and bound algorithm, which incorporates the method to obtain lower and upper bounds as well as a dominance property to reduce the search space, is suggested that gives the optimal solutions for small-sized instances. Heuristic algorithms are suggested to obtain solutions for large-sized problems within a reasonable computation time. The performances of both the optimal and heuristic algorithms, in computational experiments on randomly generated test instances, are reported.     

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 problems with random processing times under expected earliness/tardiness costs

This work is concerned with scheduling problems for a single machine. Taking earliness and tardiness of completion time and due–date value into consideration, the objective function with a common due date is considered. The processing time of each job is random. Sufficient conditions guaranteeing an optimal SEPT sequence are derived. Under exponential and normal processing times, further results are obtained     

On a single-machine optimal constant due-date assignment and sequencing problem

This paper considers the problem of optimal constant due-date assignment and sequencing of jobs in a single-machine shop. We formulate the problem as a general constrained optimization problem and apply the Kuhn-Tucker conditions to find the optimal solution which is shown to be independent of the job sequence.     

An adaptive TS approach to JIT sequencing with variable processing times and sequence-dependent setups

This paper addresses a single machine sequencing problem with variable processing times and sequence-dependent setups. The objective is to find the best trade-off between the JIT goal and the processing time compression and extension costs by simultaneously determining the job sequence and processing times for concerned jobs. Due to the combinatorial nature of the problem, it cannot be optimally solved in polynomial time. A tabu search approach is used to provide good and quick solutions. To improve the computational efficiency, an adaptive neighbourhood generation method is proposed and used in the tabu search algorithm. A total of 100 problems of different sizes have been solved to test the proposed approach. Our computational experience shows that the adaptive approach outperforms several other neighbourhood generation methods in terms of both convergence rate and solution quality. The effects of the search parameters are also discussed.     

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.     

Job sequencing and due date assignment in a single machine shop with uncertain processing times

This paper considers due date assignment and sequencing for multiple jobs in a single machine shop. The processing time of each job is assumed to be uncertain and is characterized by a mean and a variance with no knowledge of the entire distribution. A heuristic procedure is developed to find job sequence and due date assignment to minimize a linear combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. Numerical experiments indicate that the performance of the procedure is stable and robust to job processing time distributions. In addition, the performance improves when the means and variances of job processing times are uncorrelated or negatively correlated or when the penalty of a long due date assignment is significant.     

Decomposition of unreliable assembly/disassembly networks with limited buffer capacity and random processing times

An assembly/disassembly (A/D) network is a manufacturing system in which machines perform assembly and/or disassembly operations. We consider tree-structured systems of unreliable machines that produce discrete parts. Processing times, times to failure and times to repair in the inhomogeneous system are assumed to be stochastic and machine-dependent. Machines are separated by buffers of limited capacity. We develop Markov process models for discrete time and continuous time systems and derive approximate decomposition equations to determine performance measures such as production rate and average buffer levels in an iterative algorithm. An improved parameter updating procedure leads to a dramatic improvement with respect to convergence reliability. Numerical results demonstrate that the methods are quite accurate.     

Single machine scheduling when processing times are correlated normal random variables

A single machine is available to process a collection of jobs whose processing times are jointly multivariate normal. Processing is nonpreemptive. We show that in the equicorrelation case, the permutation policy which schedules the jobs in ascending order of their (marginal) mean processing times is optimal for general order-specific costs and also for job-specific costs under an agreeability condition. Suboptimality bounds on the performance of Smith's rule are obtained for the weighted flow-time criterion. A computational study shows that a dynamic version of Smith's rule comes very close to optimality.     

Particle filters with random resampling times

Particle filters are numerical methods for approximating the solution of the filtering problem which use systems of weighted particles that (typically) evolve according to the law of the signal process. These methods involve a corrective/resampling procedure which eliminates the particles that become redundant and multiplies the ones that contribute most to the resulting approximation. The correction is applied at instances in time called resampling/correction times. Practitioners normally use certain overall characteristics of the approximating system of particles (such as the effective sample size of the system) to determine when to correct the system. As a result, the resampling times are random. However, in the continuous time framework, all existing convergence results apply only to particle filters with deterministic correction times. In this paper, we analyse (continuous time) particle filters where resampling takes place at times that form a sequence of (predictable) stopping times. We prove that, under very general conditions imposed on the sequence of resampling times, the corresponding particle filters converge. The conditions are verified when the resampling times are chosen in accordance to the effective sample size of the system of particles, the coefficient of variation of the particles’ weights and, respectively, the (soft) maximum of the particles’ weights. We also deduce central-limit theorem type results for the approximating particle system with random resampling times.     

Scheduling with step-improving processing times

We consider the scheduling problem of minimizing the makespan on a single machine with step-improving job processing times around a common critical date. For this problem we give an NP-hardness proof, a fast pseudo-polynomial time algorithm, an FPTAS, and an on-line algorithm with best possible competitive ratio.     

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.     

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.     

Stationary distributions of semistochastic processes with disturbances at random times and with random severity

We consider a semistochastic continuous-time continuous-state space random process that undergoes downward disturbances with random severity occurring at random times. Between two consecutive disturbances, the evolution is deterministic, given by an autonomous ordinary differential equation. The times of occurrence of the disturbances are distributed according to a general renewal process. At each disturbance, the process gets multiplied by a continuous random variable (“severity”) supported on [0,1). The inter-disturbance time intervals and the severities are assumed to be independent random variables that also do not depend on the history.We derive an explicit expression for the conditional density connecting two consecutive post-disturbance levels, and an integral equation for the stationary distribution of the post-disturbance levels. We obtain an explicit expression for the stationary distribution of the random process. Several concrete examples are considered to illustrate the methods for solving the integral equations that occur.     

Sequencing and due-date determination in the stochastic single machine problem with earliness and tardiness costs

This paper studies the problem of simultaneous due-date determination and sequencing of a set of n jobs on a single machine where processing times are random variables and job earliness and tardiness costs are distinct. The objective is to determine the optimal sequence and the optimal due-dates which jointly minimize the expected total earliness and tardiness cost. We present an analytical approach to determine optimal due-dates, and propose two efficient heuristics of order O(n log n) to find candidates for the optimal sequence. It is demonstrated that variations in processing times increase cost and affect sequencing and due-date determination decisions. Our illustrative examples as well as computational results show that the proposed model produces optimal sequences and optimal due-dates that are significantly different from those provided by the classical deterministic single machine models. Furthermore, our computational experiments reveal that the proposed heuristics perform well in providing either optimal sequences or good candidates with low overcosts.     

Asymptotic behavior for random walk in random environment with holding times

In this article, we mainly discuss the asymptotic behavior for multi-dimensional continuous-time random walk in random environment with holding times. By constructing a renewal structure and using the point “environment viewed from the particle”, under General Kalikow's Condition, we show the law of large numbers (LLN) and central limit theorem (CLT) for the escape speed of random walk.     

Optimal task sequencing with precedence constraints

A given finite set of tasks, having known nonnegligible failure probabilities and known costs (or rewards) for their performance, can be performed sequentially until either one of the tasks fails or all tasks have been executed. The allowable task performance sequences are constrained only by certain precedence requirements, which specify that certain tasks must be performed before certain other tasks. Given the individual task failure probabilities and task costs, along with the intertask precedence requirements, the problem is to determine an optimal task performance sequence having minimal expected cost (or maximal expected reward). A number of potential applications of such “task ordering” problems are described, including R&D project organization, design of screening procedures, and determining testing points for sequential manufacturing processes.The main results of this paper are a number of reduction theorems which lead to a very efficient optimization algorithm for a large class of task ordering problems. Though these theorems are not quite sufficient for us to give a fast optimization algorithm, we do show how their use can improve upon exhaustive search techniques.     

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.     

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.