服务大规模定制模式下的供应链调度优化

为了提升服务大规模定制(SMC)模式下供应链系统的运作柔性,应对客户较强的多样化需求特征,本文在对服务定制特征分析、服务阶段界定以及服务规模效应探讨的基础上,指出SCM模式下的供应链调度问题是一个典型的随机需求与随机资源约束的多目标动态优化问题。研究了SMC模式下供应链调度的优化目标与约束条件,建立了完整的随机多目标动态调度优化数学模型。基于SMC运作的特点,运用改进的蚁群算法对调度问题进行了求解。最后,通过实例分析了模型及算法的可行性、有效性及适用性。     

基于人机交互—蚁群算法的港口疏船调度优化

为解决因港口无法正常作业导致大量船舶压港后的疏船调度问题,从同时兼顾船公司和港口方利益出发,建立了船舶平均在港时间最短、额外作业成本最低、生产秩序恢复最快的调度生产多目标优化模型。利用多属性效用理论将多目标转换为单目标,并构建了相应的评价函数,采用改进的蚁群算法并结合人机交互以及邻域搜索方法求解,最后以大连港集装箱码头实际案例进行验证。结果表明,与通常调度方法相比,文中建立的优化模型能够更好地解决疏船问题;对比常规的蚁群算法,改进后的算法搜索效率更高。上述模型和算法为集装箱码头的生产组织调度提供了新的优化思路和方法。     

具有学习-遗忘效应的半导体批调度问题研究

半导体生产制造系统具有大规模、工艺繁杂、随机性大、可重入等显著特点。以半导体最终测试阶段批处理调度为基础,把学习-遗忘效应应用到典型半导体批调度问题中,构建基于学习-遗忘效应的批调度模型。分别结合调度问题和调度模型对双层算法(粒子群算法&萤火虫算法)进行设计,通过仿真实验检验了双层算法在求解具有学习遗忘效应的批调度模型方面的可行性和有效性,并对比分析以最大完工时间为优化目标的实验结果,探讨学习遗忘效应对半导体批调度问题的影响程度,对实际半导体生产具有重要指导意义。     

不确定环境下基于时间、费用及鲁棒性权衡的多目标项目调度优化

项目调度中的时间和费用是两个重要的指标,而在不确定环境下进度计划的鲁棒性则是保证项目平稳实施的关键。本文研究不确定环境下的多目标项目调度优化问题,以优化项目的工期、鲁棒值和成本为目标安排各活动的开始时间。基于此,作者构建多目标项目调度优化模型,将模型分解为三个子模型分析目标间的权衡关系,然后设计非劣排序遗传算法进行求解,应用精英保留策略和基于子模型权衡关系的优化策略优化算法,进行算法测试和算例参数敏感性分析。最后,应用上述方法研究一个项目实例,计算得到非劣解集,实例的敏感性分析结果进一步验证了三个目标间的权衡关系,据此提出资源的有效利用策略。本文的研究可以为多目标项目调度制定进度计划提供定量化决策支持。     

基于Epsilon约束法的短纤维生产调度的双目标优化研究

针对短纤维生产行业实际,本文综合考虑客户的需求差异、客户的重要程度、纤维生产设备的准备时间以及交货期差异等因素,研究连续需求下的短纤维生产排序优化问题。首先,本文建立双目标整数规划模型,即最小化客户订单总延迟和最小化机器总准备时间;其次,设计Epsilon约束算法并调用CPLEX精确求解调度方案,即帕累托前沿;最后设计非支配排序的遗传算法(NSGA-II)求解大规模生产下的调度优化方案。通过实验,证明该整数规划模型和算法对解决多客户连续需求问题具有实际价值,进而可以为短纤维生产企业提供参考。     

汽车租赁调度多目标优化模型

本文考虑一个周期的汽车租赁调度问题,在直接调运的前提下,首先以汽车租赁公司的总收益最大和总短缺损失最小为目标,建立多目标优化模型;然后提出了基于启发式的双层排序综合择优算法;最后对汽车租赁案例进行了实证研究。     

基于多阶段模糊规模效应量化的TMC模式下供应链调度优化研究

旅游大规模定制(Tourism Mass Customization, TMC)模式实施的关键是通过对旅游供应链的调度优化处理旅游活动的“规模效应”与游客“个性化需求”之间的矛盾问题。运用经济学及模糊数学的理论方法分析并实现了TMC模式下存在的多阶段模糊规模效应量化处理。构建了引入规模效应量化的服务成本最小化、引入模糊时间窗的顾客满意度最大化及供应链协同度最大化为优化目标的TMC模式下多目标供应链调度优化模型。最后,通过蚁群算法实现TMC模式下多调度优化目标的求解并对优化效果进行对比研究。研究结果表明,TMC模式下供应链调度中旅游活动存在多阶段模糊规模效应并且可以量化处理;TMC模式中的规模效应具有合理的区间范围,旅游企业应注重规模效应与其他目标的均衡;蚂蚁算法在求解TMC模式下多目标优化问题方面不仅收敛速度快,而且通过对多调度目标优化效果的对比检验表明,性能稳健优良。     

汽车滚装码头泊位调度优化模型与算法研究

本文研究滚装码头混合泊位分配和劳动力分配的联合调度优化问题。首先,考虑潮汐时间窗约束、装卸劳动力约束、泊位缆桩分布约束以及泊位不规则布局因素,建立以最小化船舶总服务时间为目标的混合整数规划模型。其次,采用内外嵌套算法设计策略,提出求解该类问题的组合算法。其中,外层是多种群并行进化的遗传算法,生成多种船舶计划顺序,内层为基于规则的启发式算法,用于计算给定计划顺序的目标函数值。然后,基于实际运营数据,生成多组不同规模的算例进行全面数值实验,结果表明所提出的算法可在10分钟内求解包含50艘船、100个泊段的算例。最后,开展基于真实滚装码头运营实例的案例分析,对所提模型和算法在实际码头调度问题中的适用性与高效性进行验证。     

多目标资源受限项目鲁棒调度研究

由于资源受限项目调度属于NP-hard问题,传统的RCPSP主要集中于工期最短单一目标的基本问题研究,而忽略了项目调度对鲁棒性等多目标属性特征的要求。本文以经典的串行进度生成机制为基础,引入了衡量项目稳定性的鲁棒性要素,创建了项目鲁棒调度串行生成机制(RSSGS),提出了项目鲁棒性的测度新指标,构建了优化鲁棒结构的工期最短和鲁棒性最大的双目标优化模型,并结合分层优化原理,设计了改进的SA算法。最后,采用算例验证了该模型的可行性和合理性。     

考虑部分工件不可打扰的多任务调度问题研究

多任务调度问题存在于各种应用领域,如因特网服务领域,医疗领域等。经典的多任务调度模型中所有工件均可被其他等待工件打扰,且仅打扰一次。然而在生产实践过程中,有些紧急工件是不允许被其他工件打扰。在此启发下,对原有模型进行扩展,研究了在单机多任务环境下部分工件不可打扰的调度问题,模型目标包括最小化最大完工时间,最小化总完工时间,最小化最大延迟以及最小化加权提前期、拖延期和共同交货期之和。对于前三个目标给出了精确算法,对于最后一个目标给出了启发式算法。最后,对今后的研究提出了建议。     

Scheduling installations in the telecommunications industry

We develop computer-based methods for scheduling incoming work for a rapidly growing supplier of telecommunications equipment. The scheduling approach accommodates existing scheduling methodologies in the organisation along with suitable flexibility to deal with increased workloads and changing objectives. The model also facilitates the use of commercial software for the analysis of schedule information. Experimental results show that the developed algorithm outperforms existing scheduling methods.     

Exploiting process plan flexibility in production scheduling: A multi-objective approach

When solving a product/process design problem, we must exploit the available degrees of freedom to cope with a variety of issues. Alternative process plans can be generated for a given product, and choosing one of them has implications on manufacturing functions downstream, including planning/scheduling. Flexible process plans can be exploited in real time to react to machine failures, but they are also relevant for off-line scheduling. On the one hand, we should select a process plan in order to avoid creating bottleneck machines, which would deteriorate the schedule quality; on the other one we should aim at minimizing costs. Assessing the tradeoff between these possibly conflicting objectives is difficult; actually, it is a multi-objective problem, for which available scheduling packages offer little support. Since coping with a multi-objective scheduling problem with flexible process plans by an exact optimization algorithm is out of the question, we propose a hierarchical approach, based on a decomposition into a machine loading and a scheduling sub-problem. The aim of machine loading is to generate a set of efficient (non-dominated) solutions with respect to the load balancing and cost objectives, leaving to the user the task of selecting a compromise solution. Solving the machine loading sub-problem essentially amounts to selecting a process plan for each job and to routing jobs to the machines; then a schedule must be determined. In this paper we deal only with the machine loading sub-problem, as many scheduling methods are already available for the problem with fixed process plans. The machine loading problem is formulated as a bicriterion integer programming model, and two different heuristics are proposed, one based on surrogate duality theory and one based on a genetic descent algorithm. The heuristics are tested on a set of benchmark problems.     

A heuristic algorithm for a dial-a-ride problem with time windows,multiple capacities,and multiple objectives

The paper describes a system for the solution of a static dial-a-ride routing and scheduling problem with time windows (DARPTW). The problem statement and initialization of the development project was made by the Copenhagen Fire-Fighting Service (CFFS). The CFFS needed a new system for scheduling elderly and disabled persons, involving about 50.000 requests per year. The problem is characterized by, among other things, multiple capacities and multiple objectives. The capacities refer to the fact that a vehicle may be equipped with e.g. normal seats, children seats or wheel chair places. The objectives relate to a number of concerns such as e.g. short driving time, high vehicle utilization or low costs. A solution algorithm REBUS based on an insertion heuristics was developed. The algorithm permits in a flexible way weighting of the various goals such that the solution reflects the user's preferences. The algorithm is implemented in a dynamic environment intended for on-line scheduling. Thus, a new request for service is treated in less than 1 second, permitting an interactive user interface.     

A note on two-agent scheduling on an unbounded parallel-batching machine with makespan and maximum lateness objectives

This paper studies the two-agent scheduling on an unbounded parallel-batching machine. In the problem, there are two agents A and B with each having their own job sets. The jobs of a common agent can be processed in a common batch. Moreover, each agent has an objective function to be minimized. The objective function of agent A is the makespan of his jobs and the objective function of agent B is maximum lateness of his jobs. Yazdani Sabouni and Jolai [M.T. Yazdani Sabouni, F. Jolai, Optimal methods for batch processing problem with makespan and maximum lateness objectives, Appl. Math. Model. 34 (2010) 314–324] presented a polynomial-time algorithm for the problem to minimize a positive combination of the two agents’ objective functions. Unfortunately, their algorithm is incorrect. We then dwell on the problem and present a polynomial-time algorithm for finding all Pareto optimal solutions of this two-agent parallel-batching scheduling problem.     

An Optimization Based Approach to the Train Operator Scheduling Problem at Singapore MRT

Singapore Mass Rapid Transit (SMRT) operates two train lines with 83 kilometers of track and 48 stations. A total of 77 trains are in operation during peak hours and 41 during off-peak hours. In this article we report on an optimization based approach to develop a computerized train-operator scheduling system that has been implemented at SMRT. The approach involves a bipartite matching algorithm for the generation of night duties and a tabu search algorithm for the generation of day duties. The system automates the train-operator scheduling process at SMRT and produces favorable schedules in comparison with the manual process. It is also able to handle the multiple objectives inherent in the crew scheduling system. While trying to minimize the system wide crew-related costs, the system is also able to address concern with respect to the number of split duties.     

A hybrid multi-objective evolutionary algorithm based on NSGA-II for practical scheduling with release times in steel plants

The hot metal is produced from the blast furnaces in the iron plant and should be processed as soon as possible in the subsequent steel plant for energy saving. Therefore, the release times of hot metal have an influence on the scheduling of a steel plant. In this paper, the scheduling problem with release times for steel plants is studied. The production objectives and constraints related to the release times are clarified, and a new multi-objective scheduling model is built. For the solving of the multi-objective optimization, a hybrid multi-objective evolutionary algorithm based on non-dominated sorting genetic algorithm-II (NSGA-II) is proposed. In the hybrid multi-objective algorithm, an efficient decoding heuristic (DH) and a non-dominated solution construction method (NSCM) are proposed based on the problem-specific characteristics. During the evolutionary process, individuals with different solutions may have a same chromosome because the NSCM constructs non-dominated solutions just based on the solution found by DH. Therefore, three operations in the original NSGA-II process are modified to avoid identical chromosomes in the evolutionary operations. Computational tests show that the proposed hybrid algorithm based on NSGA-II is feasible and effective for the multi-objective scheduling with release times.     

Multi-objective genetic algorithm for single machine scheduling problem under fuzziness

This paper presents a new multi-objective approach to a single machine scheduling problem in the presence of uncertainty. The uncertain parameters under consideration are due dates of jobs. They are modelled by fuzzy sets where membership degrees represent decision maker’s satisfaction grade with respect to the jobs’ completion times. The two objectives defined are to minimise the maximum and the average tardiness of the jobs. Due to fuzziness in the due dates, the two objectives become fuzzy too. In order to find a job schedule that maximises the aggregated satisfaction grade of the objectives, a hybrid algorithm that combines a multi-objective genetic algorithm with local search is developed. The algorithm is applied to solve a real-life problem of a manufacturing pottery company.     

搜索区域自动变更的智能水滴算法实训课排课优化

排课问题是NP完全问题,高校实训室排课需考虑实训设备配置及教学改革"走班制"专业选修课所增加的排课复杂度.将高校实训室排课问题建模为硬约束目标及软约束优化满足问题,提出了经过改进的智能水滴算法,改进算法在路径寻优过程中根据待排课程的属性与当前排课状态,结合优化目标,自动进行跳转或围绕核心点变更搜索区域,有效解决了标准智能水滴算法搜索范围固定不利于算法搜索效率提升的问题.提出了预排序策略,减轻算法后期运行的阻力,在排课资源紧张的情况下,更好地实现收敛.通过改进智能水滴算法、标准智能水滴算法、遗传算法进行排课实验对比,验证了改进智能水滴算法在排课系统中的优化效果和高效性。     

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.