车间作业调度的可行化判定及不可行解的纠正

生产调度过程中出现不可行解是调度研究经常遇到的问题之一.提出了对JSP调度方案进行可行化判定和纠正不可行解的可行算子,算子包括了基于有向图拓扑排序原理对车间作业调度方案进行可行判定的方法和将不可行解纠正为可行解的算法.证明了该纠正算法总能成功,并对算子的功能进行了拓展使之还可应用于不完备调度.最后讨论了可行算子的特点、时间效率和应用前景.     

具有优先权和准备时间的自由作业时间表问题

研究具有优先权和准备时间的自由作业时间表问题 ,在稠密时间表的情况下 ,给出一种启发式算法 ,猜想该算法的紧界是 2 -2 /( m +1 ) ,其中 m是机器台数 .对于只有两台机器的情况 ,即当 m =2 时 ,证明该算法的最坏性能比是 4/3 ,并通过实例证明上界是紧的 .     

Surgical case scheduling as a generalized job shop scheduling problem

Surgical case scheduling allocates hospital resources to individual surgical cases and decides on the time to perform the surgeries. This task plays a decisive role in utilizing hospital resources efficiently while ensuring quality of care for patients. This paper proposes a new surgical case scheduling approach which uses a novel extension of the Job Shop scheduling problem called multi-mode blocking job shop (MMBJS). It formulates the MMBJS as a mixed integer linear programming (MILP) problem and discusses the use of the MMBJS model for scheduling elective and add-on cases. The model is illustrated by a detailed example, and preliminary computational experiments with the CPLEX solver on practical-sized instances are reported.     

遗传算法对车间作业调度的研究

应用遗传算法对车间作业调度问题进行研究,针对ＪＳＳＰ的具体特性,文中提出变异函数和二次编码的思想,获得较好的仿真结果。     

改进的混合算法求解车间作业调度问题

车间作业调度问题是个典型的NP-hard问题,为了更有效的解决车间作业调度问题,提出了一种改进的混合算法(IGASA).算法设计了一种基于当前最优解的免疫算子,算子对当前最优个体中选取运行时间最少的一台机器上的工件顺序当作疫苗,并用车间调度问题的图论模型解释了此算子的合理性.最后通过大量实验证明改进的混合算法的性能的优越性,从而证明设计的免疫算子是有意义的.     

两零售商竞争下第三方回收闭环供应链的决策及协调

为研究同时考虑零售商竞争与第三方回收闭环供应链的定价决策及协调问题, 分别建立了集中与分散决策模式下的闭环供应链优化模型, 并提出了基于改进K-S法的协调机制。研究表明:在分散式闭环供应链决策下, 较之两零售商与第三方, 制造商总是可以获得最大的利润。两零售商在产品价格上竞争程度的增强不仅可以有效提高产品销量, 同时对废旧产品的回收也起到了很好地促进作用。闭环供应链成员企业间的合作策略能有效消除系统的“双重边际”效应, 且较之零售商及第三方回收商, 制造商的合作动力更强。     

工序顺序柔性的作业车间调度问题的改进遗传算法求解

针对在工艺设计中提供工序顺序柔性的作业车间调度问题,总结了该问题中柔性工序顺序的类型和特点,并提出了一种求解该问题的改进遗传算法.以尽可能缩短制造周期为目标,结合问题特点,改进了染色体的编码方式,在常用的基于工序顺序的编码方法上融入了基于柔性工序顺序的编码方法,并据此设计了相应的交叉、变异等操作,防止遗传过程中不可行解的产生,避免染色体修复,提高求解效率.最后以MATLAB为工具用某轴承公司的实际生产数据对该算法进行了仿真.通过与不考虑工序顺序柔性的作业车间调度问题遗传算法求解结果进行对比,证明了该算法可行性和有效性.     

Parallel variable neighbourhood search algorithms for job shop scheduling problems

^** Email: msevkli{at}fatih.edu.tr^*** Corresponding author. Email: mehmetaydin{at}acm.org, mehmet.aydin{at}beds.ac.uk Variable neighbourhood search (VNS) is one of the most recentmetaheuristics used for solving combinatorial optimization problemsin which a systematic change of neighbourhood with a local searchis carried out. However, as happens with other metaheuristics,it takes a long time to reach some useful solutions while solvingsome sort of hard combinatorial problems such as job shop scheduling(JSS). Parallelization is one of the most considerable policiesto overcome this matter. In this paper, firstly, a number ofVNS algorithms are examined for JSS problems and then four differentparallelization policies are taken into account to determineefficient parallelization for VNS algorithms. The experimentationreveals the performance of various VNS algorithms and the efficiencyof policies to follow in parallelization. In the end, the unilateral-ringtopology, a noncentral parallelization method, is found as themost efficient policy.     

Open shop unit-time scheduling problems with symmetric objective functions

The paper addresses the open-shop scheduling problem with unit-time operations and nondecreasing symmetric objective function depending on job completion times. We construct two schedules, one being optimal for any symmetric convex function, the other one for any symmetric concave function. Both schedules are given by analytically defined formulas that determine in O(1) time for each operation the unit-length time slot for its processing.Received: June 2004, Revised: January 2005, AMS classification: 90B35, 68Q25     

A single server queue with cyclically indexed arrival and service rates

In this paper we consider a queueing model that results from at least two apparently unrelated areas. One motivation to study a system of this type results from a test case of a computer simulation factor screening technique calledfrequency domain methodology. A second motivation comes from manufacturing, where due to cyclic scheduling of upstream machines, the arrival process to downstream machines is periodic. The model is a single server queue with FIFO service discipline and exponential interarrival and service times where the arrival and/or service rates are deterministic cyclic functions of the customer sequence number. We provide steady state results for the mean number in the system for the model with cyclic arrival and fixed service rates and for the model with fixed arrival and cyclic service rates. For the model with both cyclic arrival and service rates, upper and lower bounds are developed for the steady state mean waiting time in the system. Throughout the paper various implications and/or insights derived from the results of this study are discussed for frequency domain methodology.The authors acknowledge the financial support of the CBA/GSB Faculty Research Committee of the College of Business Administration, The University of Texas at Austin.     

A Computational Study of Shifting Bottleneck Procedures for Shop Scheduling Problems

We examine the performance of Shifting Bottleneck (SB) heuristics for shop scheduling problems where the performance measure to be minimized is makespan (C _max) or maximum lateness (L _max). Extensive computational experiments are conducted on benchmark problems from the literature as well as several thousand randomly generated test problems with three different routing structures and up to 1000 operations. Several different versions of SB are examined to determine the effect on solution quality and time of different subproblem solution procedures, reoptimization procedures and bottleneck selection criteria. Results show that the performance of SB is significantly affected by job routings, and that SB with optimal subproblem solutions and full reoptimization at each iteration consistently outperforms dispatching rules, but requires high computation times for large problems. High quality subproblem solutions and reoptimization procedures are essential to obtaining good solutions. We also show that schedules developed by SB to minimize L _max perform well with respect to several other performance measures, rendering them more attractive for practical use.     

Surrogate Gradient Algorithm for Lagrangian Relaxation

The subgradient method is used frequently to optimize dual functions in Lagrangian relaxation for separable integer programming problems. In the method, all subproblems must be solved optimally to obtain a subgradient direction. In this paper, the surrogate subgradient method is developed, where a proper direction can be obtained without solving optimally all the subproblems. In fact, only an approximate optimization of one subproblem is needed to get a proper surrogate subgradient direction, and the directions are smooth for problems of large size. The convergence of the algorithm is proved. Compared with methods that take effort to find better directions, this method can obtain good directions with much less effort and provides a new approach that is especially powerful for problems of very large size.     

Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function

The paper present a linear-time algorithm for solving the two machine open shop scheduling problem to minimize an arbitrary regular penalty function depending on the lengths of periods during which the machines are used. Both the preemptive and the nonpreemptive cases of the problem are considered.     

An integrated approach for scheduling health care activities in a hospital

To effectively utilise hospital beds, operating rooms (OR) and other treatment spaces, it is necessary to precisely plan patient admissions and treatments in advance. As patient treatment and recovery times are unequal and uncertain, this is not easy. In response, a sophisticated flexible job-shop scheduling (FJSS) model is introduced, whereby patients, beds, hospital wards and health care activities are respectively treated as jobs, single machines, parallel machines and operations. Our approach is novel because an entire hospital is describable and schedulable in one integrated approach. The scheduling model can be used to recompute timings after deviations, delays, postponements and cancellations. It also includes advanced conditions such as activity and machine setup times, transfer times between activities, blocking limitations and no wait conditions, timing and occupancy restrictions, buffering for robustness, fixed activities and sequences, release times and strict deadlines. To solve the FJSS problem, constructive algorithms and hybrid meta-heuristics have been developed. Our numerical testing shows that the proposed solution techniques are capable of solving problems of real world size. This outcome further highlights the value of the scheduling model and its potential for integration into actual hospital information systems.     

Set-Up Coordination between Two Stages of a Supply Chain

In the material flow of a plant, parts are processed in batches, each having two distinct attributes, say shape and color. In one department, a set-up occurs every time the shape of the new batch is different from the previous one. In a downstream department, there is a set-up when the color of the new batch is different from the previous one. Since a unique sequence of batches must be established, the problem consists in finding such a common sequence optimizing an overall utility index. Here we consider two indices, namely the total number of set-ups and the maximum number of set-ups between the two departments. Both problems are shown to be NP-hard. An efficient heuristic approach is presented for the first index which allows to solve a set of real-life instances and performs satisfactorily on a large sample of experimental data.     

带强制工期的双机开放车间排序问题

讨论了强制工期相等的n个工件在双机开放车间加工.在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,同题可能会无可行排序.先讨论了问题的可行性.如果问题可行,找出一个可行序列作为预排序列,并提出了一个算法计算每个工件尽可能迟的开工时间.而后,提出了一个多项式时间最优算法,在预排序列的基础上,通过调整两台机器上最先加工的工件来获得最优排序.     

一种多策略引导的电磁场优化算法求解作业车间调度问题

电磁场优化算法是目前一种比较新颖的群智能优化算法,其利用不同极性电磁场所产生的引斥力,使电磁粒子朝最优解移动。针对标准电磁场优化算法在求解作业车间调度问题时容易陷入局部极值点、收敛精度差等问题,提出了一种多策略引导的电磁场优化算法。算法中粒子受到三种不同来源的引斥力,在迭代过程中通过计算每种移动策略的临代电差、累计电差和综合电差来决定粒子的引导方式,并通过概率变异算法来避免陷入局部最优解。通过作业车间调度问题FT、LA系列测试实例仿真实验,对新算法与其他算法的测试结果进行比较分析,研究表明该算法具有更高的求解精度和更快的计算速度。     

带有机器维修和两车辆派送的单机排序问题

研究了带有机器维修和工件派送的单机排序问题,该问题可以被视为一个集成生产和出站配送的排序模型。不同体积的工件需要在带有一个维修区间的机器上加工,且加工不可中断,然后由固定容量的两辆同类车批次交付给单客户,目标函数是极小化最大完工时间,本文提出了2-近似算法,并证明了2是紧界。     

一个非常规目标函数的单机随机调度的最优策略

本文考虑了n个工件在同一台机器上加工的调度问题 ,其中工件的加工时间和交货期都是具有任意分布的随机变量 .我们考虑了一个非常规目标函数 ,其中工件的权数与平均加工时间成比例 .在工件的交货期与加工时间满足相容条件下 ,得到了个简单的最优排序策略 .     

Lower Bounds for Scheduling a Single Robot in a Job-Shop Environment

We consider a single-machine scheduling problem which arises as a subproblem in a job-shop environment where the jobs have to be transported between the machines by a single transport robot. The robot scheduling problem may be regarded as a generalization of the traveling salesman problem with time windows, where additionally generalized precedence constraints (minimal time-lags) have to be respected. The objective is to determine a sequence of all nodes and corresponding starting times in the given time windows in such a way that all generalized precedence relations are respected and the sum of all traveling and waiting times is minimized.We calculate lower bounds for this problem using constraint propagation techniques and a linear programming formulation which is solved by a column generation procedure. Computational results are presented for test data arising from job-shop instances with a single transport robot and some modified traveling salesman instances.