Scheduling jobs on a machine subject to stochastic breakdowns to minimize absolute early-tardy penalties

This article addresses the problem of scheduling n jobs with a common due date on a machine subject to stochastic breakdowns to minimize absolute early-tardy penalties.We investigate the problem under the conditions that the uptimes follow an exponential distribution,and the objective measure in detail is to minimize the expected sum of the absolute deviations of completion times from the common due date.We proceed to study in two versions (the downtime follows an exponential distribution or is a constant entailed for the repeat model job),one of which is the so-called preempt- resume version,the other of which is the preempt-repeat version.Three terms of work have been done.(i)Formulations and Preliminaries.A few of necessary definitions,relations and basic facts are established.In particular,the conclusion that the expectation of the absolute deviation of the completion time about a job with deterministic processing time t from a due date is a semi-V-shape function in t has been proved.(ii) Properties of Optimal Solutions.A few characteristics of optimal solutions are established.Most importantly,the conclusion that optimal solutions possess semi-V- shape property has been proved.(iii) Algorithm.Some computing problems on searching for optimal solutions are discussed.     

Single machine stochastic JIT scheduling problem subject to machine breakdowns

In this paper we research the single machine stochastic JIT scheduling problem subject to the machine breakdowns for preemptive-resume and preemptive-repeat.The objective function of the problem is the sum of squared deviations of the job-expected completion times from the due date.For preemptive-resume,we show that the optimal sequence of the SSDE problem is V-shaped with respect to expected processing times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.We discuss the difference between the SSDE problem and the ESSD problem and show that the optimal solution of the SSDE problem is a good approximate optimal solution of the ESSD problem,and the optimal solution of the SSDE problem is an optimal solution of the ESSD problem under some conditions.For preemptive-repeat,the stochastic JIT scheduling problem has not been solved since the variances of the completion times cannot be computed.We replace the ESSD problem by the SSDE problem.We show that the optimal sequence of the SSDE problem is V-shaped with respect to the expected occupying times.And a dynamic programming algorithm with the pseudopolynomial time complexity is given.A new thought is advanced for the research of the preemptive-repeat stochastic JIT scheduling problem.     

Minimizing makespan on a single machine subject to random breakdowns

We investigate optimal sequencing policies for the expected makespan problem with an unreliable machine, where jobs have to be reprocessed in their entirety if preemptions occur because of breakdowns. We identify a class of uptime distributions under which LPT minimizes expected makespan.     

A hybrid genetic algorithm with dominance properties for single machine scheduling with dependent penalties

In this paper, a hybrid genetic algorithm is developed to solve the single machine scheduling problem with the objective to minimize the weighted sum of earliness and tardiness costs. First, dominance properties of (the conditions on) the optimal schedule are developed based on the switching of two adjacent jobs i and j. These dominance properties are only necessary conditions and not sufficient conditions for any given schedule to be optimal. Therefore, these dominance properties are further embedded in the genetic algorithm and we call it genetic algorithm with dominance properties (GADP). This GADP is a hybrid genetic algorithm. The initial populations of schedules in the genetic algorithm are generated using these dominance properties. GA can further improve the performance of these initial solutions after the evolving procedures. The performances of hybrid genetic algorithm (GADP) have been compared with simple genetic algorithm (SGA) using benchmark instances. It is shown that this hybrid genetic algorithm (GADP) performs very well when compared with DP or SGA alone.     

Scheduling a single machine to minimize earliness penalties subject to the SLK due-date determination method

This paper considers a single machine scheduling problem. There are n jobs to be processed on a single machine. The problem is to minimize total earliness penalties subject to no tardy jobs. The problem is NP-complete if the due-dates are arbitrary. We study the problem when the due-dates are determined by the equal slack (SLK) method. Two special cases of the problem are solved in polynomial time. The first one is the problem with equally weighted monotonous penalty objective function. The second one is the problem with weighted linear penalty objective function.     

Complexity of single machine scheduling subject to nonnegative inventory constraints

This paper focuses on single machine scheduling subject to inventory constraints. Jobs either add items to an inventory or remove items from that inventory. Jobs that have to remove items cannot be processed if the required number of items is not available. We consider scheduling problems on a single machine with the minimization of the total weighted completion time, the maximum lateness, and the number of tardy jobs, respectively, as objective and determine their computational complexity. Since the general versions of our problems turn out to be strongly NP-hard, we consider special cases by assuming that different jobs have certain parameter values in common. We determine the computational complexity for all special cases when the objective is either to minimize total completion time or to minimize maximum lateness and for several special cases when the objective is either to minimize total weighted completion time or to minimize the number of tardy jobs.     

On the single server retrial queue subject to breakdowns

This paper deals with a single server retrial queueing system subject to active and independent breakdowns. The objective is to extend the results given independently by Aissani [1] and Kulkarni and Choi [15]. To this end, we introduce the concept of fundamental server period and an auxiliary queueing system with breakdowns and option for leaving the system. Then, we concentrate our attention on the limiting distribution of the system state. We obtain simplified expressions for the partial generating functions of the server state and the number of customers in the retrial group, a recursive scheme for computing the limiting probabilities and closed-form formulae for the second order partial moments. Some stochastic decomposition results are also investigated. This revised version was published online in June 2006 with corrections to the Cover Date.     

Single machine scheduling with flow time and earliness penalties

This paper considers the problem of schedulingn jobs on a single machine to minimize the total cost incurred by their respective flow time and earliness penalties. It is assumed that each job has a due date that must be met, and that preemptions are not allowed. The problem is formulated as a dynamic program (DP) and solved with a reaching algorithm that exploits a series of dominance properties and efficiently generated bounds. A major factor underlying the effectiveness of the approach is the use of a greedy randomized adaptive search procedure (GRASP) to construct high quality feasible solutions. These solutions serve as upper bounds on the optimum, and permit a predominant portion of the state space to be fathomed during the DP recursion.To evaluate the performance of the algorithm, an experimental design involving over 240 randomly generated problems was followed. The test results indicate that problems with up to 30 jobs can be readily solved on a microcomputer in less than 12 minutes. This represents a significant improvement over previously reported results for both dynamic programming and mixed integer linear programming approaches.     

Efficient algorithms for machine scheduling problems with earliness and tardiness penalties

In this paper, we study the multi-machine scheduling problem with earliness and tardiness penalties and sequence dependent setup times. This problem can be decomposed into two subproblems—sequencing and timetabling. Sequencing focuses on assigning each job to a fixed machine and determine the job sequence on each machine. We call such assignment a semi-schedule. Timetabling focuses on finding an executable schedule from the semi-schedule via idle-time insertion. Sequencing is strongly NP-hard in general. Although timetabling is polynomial-time solvable, it can become a computational bottleneck if the procedure is executed many times within a larger framework. This paper makes two contributions. We first propose a quantum improvement to the computational efficiency of the timetabling algorithm. We then apply it within a squeaky wheel optimization framework to solve the sequencing and overall problem. Finally, we demonstrate the strength of our proposed algorithms by experiments.     

Single machine scheduling with symmetric earliness and tardiness penalties

This research focuses on scheduling jobs with varying processing times and distinct due dates on a single machine subject to earliness and tardiness penalties. Hence, this work will find application in a just-in-time (JIT) production environment. The scheduling problem is formulated as a 0–1 linear integer program with three sets of constraints, where the objective is to minimize the sum of the absolute deviations between job completion times and their respective due dates. The first two sets of constraints are equivalent to the supply and demand constraints of an assignment problem. The third set, which represents the process time non-overlap constraints, is relaxed to form the Lagrangian dual problem. The dual problem is then solved using the subgradient algorithm. Efficient heuristics have also been developed in this work to yield initial primal feasible solutions and to convert primal infeasible solutions to feasibility. The computational results show that the relative deviation from optimality obtained by the subgradient algorithm is less than 3% for problem sizes varying from 10 to 100 jobs.     

Assessing the effects of machine breakdowns in stochastic scheduling

In most scheduling problems discussed in the literature it is assumed that the machine (i.e. key resource) is continuously available. Plainly, this is often unrealistic. Here we suggest assessing the effects of machine breakdowns by evaluating the strategy which is optimal when the machine is always available as a strategy for the breakdowns case. The results extend earlier ones of the authors and co-workers.     

Single machine scheduling subject to precedence delays

A single-machine scheduling problem with precedence delays is analyzed. A set of n tasks is to be scheduled on the machine in such a way that the makespan is minimized. The executions of the tasks are constrained by precedence delays, i.e., a task can start its execution only after any of its predecessors has completed and the delay between the two tasks has elapsed. In the case of unit execution times and integer lengths of delays, the problem is shown to be NP-hard in the strong sense. In the case of integer execution times and unit length of delays, the problem is polynomial, and an O(n²) optimal algorithm is provided. Both preemptive and non-preemptive cases are considered.     

Cost analysis of the unloader queueing system with a single unloader subject to breakdowns

In this paper, we deal with an unloader queueing model in which N identical trailers are unloaded by a single unloader. We consider two different types of a single unloader, which are subject to breakdowns. In type 1, the unloader can break down only when there is at least one trailer in the system, while in type 2, the unloader can break down even if no trailers are in the system. Analytic closed-form solutions of the unloader queueing system are derived. A cost model is developed in order to determine the optimal value of the number of trailers to be assigned to the unloader for both types. Under the optimal operating condition, numerical results are presented in which several system performance measures are evaluated based on assumed numerical values given to the system parameters. Sensitivity analysis is also investigated.     

Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties

In this paper we consider parallel identical machines scheduling problems with deteriorating jobs. In this model, job processing times are defined by functions of their starting times. We concentrate on two goals separately, namely, minimizing the total absolute differences in completion times (TADC) and the total absolute differences in waiting times (TADW). We show that the problems remains polynomially solvable under the proposed model.     

Solution of the generalized Townsend single machine scheduling model

The paper deals with the generalized version of Townsend's n-job single machine scheduling model. It shows that the model is highly decomposable for n = 20, 50 and 100 when all its parameters are drawn from the same uniform distribution. It identifies a less decomposable version and provides an improved branching method to solve it. This method is tested on problems of size n = 20 and 50 on a PC and n = 100 on a mainframe computer.     

An approach to predictive-reactive scheduling of parallel machines subject to disruptions

In this paper, a new predictive-reactive approach to a parallel machine scheduling problem in the presence of uncertain disruptions is presented. The approach developed is based on generating a predictive schedule that absorbs the effects of possible uncertain disruptions through adding idle times to the job processing times. The uncertain disruption considered is material shortage, described by the number of disruption occurrences and disruption repair period. These parameters are specified imprecisely and modelled using fuzzy sets. If the impact of a disruption is too high to be absorbed by the predictive schedule, a rescheduling action is carried out. This approach has been applied to solving a real-life scheduling problem of a pottery company.     

Minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint

In this paper, we consider the problem of minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint. A key difficulty with this problem is its nonconvexity. Using Lagrange duality, we show that under a mild assumption, this problem can be solved by solving a linearly constrained convex univariate minimization problem. Finally, the superior efficiency of the new approach compared to the known semidefinite relaxation and a known approach from the literature is demonstrated by solving several randomly generated test problems.     

Stochastic single machine scheduling problem as a multi-stage dynamic random decision process

In this work, we study a stochastic single machine scheduling problem in which the features of learning effect on processing times, sequence-dependent setup times, and machine configuration selection are considered simultaneously. More precisely, the machine works under a set of configurations and requires stochastic sequence-dependent setup times to switch from one configuration to another. Also, the stochastic processing time of a job is a function of its position and the machine configuration. The objective is to find the sequence of jobs and choose a configuration to process each job to minimize the makespan. We first show that the proposed problem can be formulated through two-stage and multi-stage Stochastic Programming models, which are challenging from the computational point of view. Then, by looking at the problem as a multi-stage dynamic random decision process, a new deterministic approximation-based formulation is developed. The method first derives a mixed-integer non-linear model based on the concept of accessibility to all possible and available alternatives at each stage of the decision-making process. Then, to efficiently solve the problem, a new accessibility measure is defined to convert the model into the search of a shortest path throughout the stages. Extensive computational experiments are carried out on various sets of instances. We discuss and compare the results found by the resolution of plain stochastic models with those obtained by the deterministic approximation approach. Our approximation shows excellent performances both in terms of solution accuracy and computational time.

     

Production planning and pricing policy in a make-to-stock system with uncertain demand subject to machine breakdowns

We consider a make-to-stock system served by an unreliable machine that produces one type of product, which is sold to customers at one of two possible prices depending on the inventory level at the time when a customer arrives (i.e., the decision point). The system manager must determine the production level and selling price at each decision point. We first show that the optimal production and pricing policy is a threshold control, which is characterized by three threshold parameters under both the long-run discounted profit and long-run average profit criteria. We then establish the structural relationships among the three threshold parameters that production is off when inventory is above the threshold, and that the optimal selling price should be low when inventory is above the threshold under the scenario where the machine is down or up. Finally we provide some numerical examples to illustrate the analytical results and gain additional insights.