有根森林优先约束的单机随机排序问题

讨论单机随机排序问题,目标函数为确定工件的排列顺序使工件的加权完工时间和的数学期望最小.设工件间的优先约束为有根森林,机器发生随机故障.对此情况,给出了多项式时间的最优算法.     

带运输机的流水车间调度的最优算法

研究带运输时间的流水调度:在该问题中有两台机器A,B和一个运输机V,n个工件,工件需要先在机器A上加工然后在机器B上加工最后被运输机V运往目的地,而且运输机V最初停在机器B旁边.模型的目标是使所有工件都运往目的地的时间最短.文中给出了三种情况下的最优调度算法:i)A,B机器加工工件顺序给定时我们给出了线性时间的最优算法;ii)所有的工件加工时间在机器B上时间相等时我们给出了时间复杂度为O(nlogn)的最优算法;iii)机器B上工件最短加工时间大于等于机器A上工件最长加工时间时给出了时间复杂度为O(n~2)的最优算法.     

具有优先约束的单机随机排序问题

讨论工件的加工时间为常数,机器发生随机故障的单机随机排序问题,目标函数极小化工件的加权完工时间和的数学期望最小.考虑两类优先约束模型.在第一类模型中,设工件间的约束为串并有向图.证明了模块M的ρ因子最大初始集合I中的工件优先于模块中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到机器发生随机故障的情况.在第二类模型中,设工件间的约束为出树优先约束.证明了最大家庭树中的工件优先于家庭树中其它的工件加工,并且其工件连续加工所得到的排序为最优排序并给出了最优算法.     

带机器故障的两台机带权误工数排序问题

讨论机器带故障中断的两台平行机排序问题,工件加工时间均为单位时间,目标是极小化带权误工工件数.当转移时间t=0时给出了最优的算法.当t≠0时,给出了一个多项式时间的近似算法,并证明算法解与最优解至多相差一个带权误工数.     

带两个服务等级的三台机最优在线算法

研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.     

工件间具有串并有向图约束的单机随机排序问题

研究机器发生随机故障的单机排序问题,其中工件间的优先约束为串并有向图,目标函数为极小化加权完工时间和,证明了此问题多项式时间可解,并给出了多项式时间算法.     

具有学习和退化效应的单机干扰管理问题

针对工件同时具有学习和退化效应、机器具有可用性限制这一问题,建立可预见性单机干扰管理模型。在这一模型中,工件的加工时间是既与工件所排的加工位置又与工件开始加工的时间有关的函数。同时,在生产过程中由于机器发生故障或定期维修等扰动事件导致机器在某段时间内不能加工工件。目标是在同时考虑原目标函数和由扰动造成的偏离函数的情况下,构建一个新的最优时间表序列。根据干扰度量函数的不同研究了两个问题,第一个问题的目标函数是极小化总完工时间与总误工时间的加权和;第二个问题的目标函数是极小化总完工时间与总提前时间的加权和。对于所研究的问题,首先证明了最优排序具有的性质,然后建立了相应的拟多项式时间动态规划算法。     

一类随机完工时间二阶矩的表示方法

给出一种运用机器的工作时间、故障时间和工件的加工时间的分布特征表示在一台具有Birge所定义的序列随机故障的机器上加工一个中断-重复型工件的完工时间的二阶矩的方法, 并通过举例说明所建立的表示在风险分析与决策优化方面的应用.     

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

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

机器具有学习效应的供应链排序问题

研究了机器具有学习效应的供应链排序问题.有多个客户分布在不同位置,每个客户都有一定数量的工件需要在一台机器上进行加工.每个客户的工件在机器上加工时具有学习效应,即后面加工的工件实际加工时间是逐渐缩短的.工件生产完后需要运输到相应的客户处,每一批配送需要花费一定的时间和费用.这里研究了供应链排序理论中主要的四个目标函数,分析了这些问题的复杂性,对于一些情况给出了它们的最优算法.     

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.     

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.

     

A contribution to the stochastic flow shop scheduling problem

This paper deals with performance evaluation and scheduling problems in m machine stochastic flow shop with unlimited buffers. The processing time of each job on each machine is a random variable exponentially distributed with a known rate. We consider permutation flow shop. The objective is to find a job schedule which minimizes the expected makespan. A classification of works about stochastic flow shop with random processing times is first given. In order to solve the performance evaluation problem, we propose a recursive algorithm based on a Markov chain to compute the expected makespan and a discrete event simulation model to evaluate the expected makespan. The recursive algorithm is a generalization of a method proposed in the literature for the two machine flow shop problem to the m machine flow shop problem with unlimited buffers. In deterministic context, heuristics (like CDS [Management Science 16 (10) (1970) B630] and Rapid Access [Management Science 23 (11) (1977) 1174]) and metaheuristics (like simulated annealing) provide good results. We propose to adapt and to test this kind of methods for the stochastic scheduling problem. Combinations between heuristics or metaheuristics and the performance evaluation models are proposed. One of the objectives of this paper is to compare the methods together. Our methods are tested on problems from the OR-Library and give good results: for the two machine problems, we obtain the optimal solution and for the m machine problems, the methods are mutually validated.     

Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem

We study a static stochastic single machine scheduling problem in which jobs have random processing times with arbitrary distributions, due dates are known with certainty, and fixed individual penalties (or weights) are imposed on both early and tardy jobs. The objective is to find an optimal sequence that minimizes the expected total weighted number of early and tardy jobs. The general problem is NP-hard to solve; however, in this paper, we develop certain conditions under which the problem is solvable exactly. An efficient heuristic is also introduced to find a candidate for the optimal sequence of the general problem. Our illustrative examples and computational results demonstrate that the heuristic performs well in identifying either optimal sequences or good candidates with low errors. Furthermore, we show that special cases of the problem studied here reduce to some classical stochastic single machine scheduling problems including the problem of minimizing the expected weighted number of early jobs and the problem of minimizing the expected weighted number of tardy jobs which are both solvable by the proposed exact or heuristic methods.     

Machine scheduling with an availability constraint

Most literature in scheduling assumes that machines are available simultaneously at all times. However, this availability may not be true in real industry settings. In this paper, we assume that the machine may not always be available. This happens often in the industry due to a machine breakdown (stochastic) or preventive maintenance (deterministic) during the scheduling period. We study the scheduling problem under this general situation and for the deterministic case.We discuss various performance measures and various machine environments. In each case, we either provide a polynomial optimal algorithm to solve the problem, or prove that the problem is NP-hard. In the latter case, we develop pseudo-polynomial dynamic programming models to solve the problem optimally and/or provide heuristics with an error bound analysis.This research was supported in part by NSF grant DDM 9201627     

Stochastic scheduling to minimize expected maximum lateness

This paper is concerned with the problems in scheduling a set of jobs associated with random due dates on a single machine so as to minimize the expected maximum lateness in stochastic environment. This is a difficult problem and few efforts have been reported on its solution in the literature. In this paper, we first derive a deterministic equivalent to the expected maximum lateness and then propose a dynamic programming algorithm to obtain the optimal solutions. The procedures to compute optimal solutions are initially developed in the case of deterministic processing times, and then extended to stochastic processing times following arbitrary probability distributions. Moreover, several heuristic rules are suggested to compute near-optimal solutions, which are shown to be highly efficient and accurate by computer-based experiments.     

Time complexity of single- and identical parallel-machine scheduling with GERT network precedence constraints

In this paper we deal with the time complexity of single- and identical parallel-machine scheduling problems in which the durations and precedence constraints of the activities are stochastic. The stochastic precedence constraints are given by GERT networks. First, we sketch the basic concepts of GERT networks and machine scheduling with GERT network precedence constraints. Second, we discuss the time complexity of some open single-machine scheduling problems with GERT network precedence constraints. Third, we investigate the time complexity of identical parallel-machine scheduling problems with GERT network precedence constraints. Finally, we present an efficient reduction algorithm for the problem of computing the expected makespan for the latter type of scheduling problem.     

Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs

This paper studies the parallel machines bi-criteria scheduling problem (PMBSP) in a deteriorating system. Sequencing and scheduling problems (SSP) have seldom considered the two phenomena concurrently. This paper discusses the parallel machines scheduling problem with the effects of machine and job deterioration. By the machine deterioration effect, we mean that each machine deteriorates at a different rate. This deterioration is considered in terms of cost which depends on the production rate, the machine’s operating characteristics and the kind of work done by each machine. Moreover, job processing times are increasing functions of their starting times and follow a simple linear deterioration. The objective functions are minimizing total tardiness and machine deteriorating cost. The problem of total tardiness on identical parallel machines is NP-hard, thus the problem with machine deteriorating cost as an additional term is also NP-hard. We propose the LP-metric method to show the importance of our proposed multi-objective problem. A metaheuristic algorithm is developed to locate optimal or near optimal solutions based on a Tabu search mechanism. Numerical examples are presented to show the efficiency of this model.