带有资源分配和恶化工件的单机多任务排序问题研究

研究了带有公共交货期的单机多任务排序问题,考虑了两种不同的资源分配函数和位置相关恶化效应函数,目标是找到一个排序和共同的交货期,使得提前、拖期、交货期和资源成本最小,设计了多项式时间算法.针对一个特殊情形,给出了更有效的算法.     

具有非对称模糊加工时间工期指派调度优化问题的一类加权模型及其求解算法

根据模糊变量截集所表达的信息的重要程度,建立了模糊环境下工期指派调度优化问题的一类加权模型,该模型中工件加工时间为非对称三角模糊数,目标函数为极小化提前完工惩罚和拖期完工惩罚和的加权可能性均值.证明了当工件加工时间具有相同宽度比时,模型是多项式可解的,并给出了求解的多项式算法.数值实验表明加权模型与现有的非加权模型相比能有效的降低总费用.     

模糊生产系统中的多类型差异作业平行机批调度优化

针对现实生产制造系统中存在的时间参数模糊化问题,采用梯形模糊数表征时间参数,给出了一种具有模糊加工时间、模糊交货期与模糊批次间隔的,以最小化制造跨度和最小化提前/拖期惩罚为目标的多类型差异作业平行机批调度问题模型。在问题求解方面,给出了一种具有量子行为的,采用混沌局部优化的混合粒子群算法,避免求解过程陷入局部最优。仿真实验验证了该算法具有可行性和有效性。     

基于仿真优化的炼钢生产批调度求解方法

论文针对钢铁企业炼钢工序具有高温、高能耗、复杂工况的实际特征,从中提炼出生产批调度问题,其工件根据其实际工艺属性可分为多个簇,基于给定的工件簇,决策工件的分批和调度情况,综合考虑工件之间的切换费用,以及工件提前、拖期所导致的惩罚,使得总的生产成本期望最小化,从而降低生产成本;针对该问题,考虑工件的处理时间、工件的加工属性具有不确定性,基于仿真优化思想,建立数学模型,并基于大数定理,对模型目标函数进行近似;提出基于样本近似方法的求解框架,通过随机抽样的方法获得不同规模的样本,针对不同规模的样本,提出Filter & Fan算法对问题进行求解;最后,通过基于实际数据的计算实验验证所提算法的有效性。     

多时间窗车辆路径问题的智能水滴算法

研究了多时间窗车辆路径问题,考虑了车容量、多个硬时间窗限制等约束条件,以动用车辆的固定成本和车辆运行成本之和最小为目标,建立了整数线性规划模型。根据智能水滴算法的基本原理,设计了求解多时间窗车辆路径问题的快速算法,利用具体实例进行了模拟计算,并与遗传算法的计算结果进行了对比分析,结果显示,利用智能水滴算法求解多时间窗车辆路径问题,能够以很高的概率得到全局最优解,是求解多时间窗车辆路径问题的有效算法。     

混流无等待流水线批次批量生产计划方法

在两阶段混流无等待流水装配环境下,为解决任务组批生产导致的订单按期交付能力弱,以及产品需求与部件供应无法准确衔接的问题,以最小化在制品库存成本和产品提前拖期惩罚为目标,建立了两阶段批次批量生产计划数学模型。设计了双目标蚁群求解算法,构造了每只蚂蚁对不同目标的偏重算子,以及基于批次的可行解生成方法和信息素更新机制,提高了解的局部和全局搜索能力。通过与NSGA-II进行对比,验证了本算法在同等时间内计算精度优于后者,为提高两阶段多条生产线组批生产计划的可执行性提供方法支持。     

考虑订单取件时间和柔性时间窗的取送货车辆路径问题

研究了同城配送中考虑订单取货时间和柔性时间窗的取送货车辆路径问题,考虑同城配送中订单起终点,订单取货时间和订单配送的柔性时间窗,车容量限制等因素。首先构建以配送成本与超时惩罚成本之和最小化为目标的混合整数线性模型。其次,设计了含多种有效不等式及其对应分离算法的改进分支切割算法对该模型进行精确求解。最后通过实验测试分析了不等式的性能,验证了算法的有效性,实验表明适当的减少车辆数和增大装载能力能够有效的减少成本。     

主通道位置不固定的设施布局问题多目标优化模型及算法

以物流中心设施布局问题为对象,提出了考虑出入口及主通道位置不固定情况下的设施布局问题的多目标优化模型并设计了其改进的遗传算法。首先,以物料搬运成本最小、活动关系密切度最大和面积利用率最大为目标,构建了考虑出入口位置不固定条件下的具有I型主通道的设施布局多目标优化数学模型。然后,设计了一种改进的遗传算法,包括:改进的编码、解码方法,追加了解码修正操作,基于惩罚函数策略的适应度函数等。实例测试表明,本算法的执行效率高而且结果稳定,优化效果好,布局结果紧凑适用。     

带有时间窗的生鲜物流配送路径优化研究

随着生鲜消费的日益增多,生鲜物流配送也面临着如何在快速安全的条件下满足人们对生鲜的需求,使消费者在最短的时间得到最新鲜产品的现实问题,提出带有时间窗的生鲜物流配送车辆路径问题.充分考虑配送距离、车辆固定成本、生鲜损耗等多种因素,设计以配送损耗为可变成本和车辆启动费用为固定成本之和最小的优化目标,建立带有时间窗生鲜损耗的配送模型.针对模型的特征,设计自适应遗传算法求解该模型.最后,结合仿真算例来验证模型与算法的有效性.     

双目标可重入混合流水车间调度问题的离散灰狼优化算法

可重入混合流水车间调度问题普遍存在于许多高科技制造产业中,如半导体晶圆制造和TFT-LCD面板生产过程等,但目前关于可重入调度问题的相关研究还比较少。本文设计了一种改进多目标灰狼优化算法(IMOGWO)解决最小化最大完工时间和总拖期时间最小的可重入混合流水车间调度问题,针对该问题特点对基本灰狼优化算法进行了一系列改进操作。通过对小规模测试问题基准算例的数值实验,验证了所设计的IMOGWO算法求解该调度问题的有效性。实验结果表明IMOGWO算法在非劣解的收敛性和支配性方面显著优于已有的NSGA-II和MOGWO算法,在解的分布性指标方面IMOGWO稍微优于其他两种算法。     

Parallel machine scheduling with a common due window

In this paper, we consider a machine scheduling problem where jobs should be completed at times as close as possible to their respective due dates, and hence both earliness and tardiness should be penalized. Specifically, we consider the problem with a set of independent jobs to be processed on several identical parallel machines. All the jobs have a given common due window. If a job is completed within the due window, then there is no penalty. Otherwise, there is either a job-dependent earliness penalty or a job-dependent tardiness penalty depending on whether the job is completed before or after the due window. The objective is to find an optimal schedule with minimum total earliness–tardiness penalty. The problem is known to be NP-hard. We propose a branch and bound algorithm for finding an optimal schedule of the problem. The algorithm is based on the column generation approach in which the problem is first formulated as a set partitioning type formulation and then in each branch and bound iteration the linear relaxation of this formulation is solved by the standard column generation procedure. Our computational experiments show that this algorithm is capable of solving problems with up to 40 jobs and any number of machines within a reasonable computational time.     

优化交货期窗口的两阶段供应链排序问题

研究一类优化交货期窗口的两阶段供应链排序问题. 优化交货期窗口是指交货期窗口的开始与结束时刻是决策变量, 不是输入常量. 两阶段是指工件先加工, 后运输: 加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件. 工件的开始运输时刻与完工时刻之差定义为工件的储存时间, 且有相应的储存费用. 若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻, 则有相应的提前(延误)惩罚费用. 目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和. 针对单位时间的延误惩罚费用不超过单位时间的储存费用、单位时间的储存费用不超过单位时间的提前惩罚费用的情形, 给出了时间复杂性为O(n^{8})的动态规划算法.     

储存时间有上限的两阶段供应链排序问题

研究一类储存时间有上限的两阶段供应链排序问题.两阶段是指工件先加工,后运输:加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件.工件的运输完成时刻与完工时刻之差定义为工件的储存时间,且有相应的储存费用,且任意工件的储存时间都不超过某一常数.若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻,则有相应的提前(延误)惩罚费用.目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和.先证明该问题是NP-难的,后对单位时间的储存费用不超过单位时间的延误惩罚费用的情形给出了伪多项式时间算法.     

Single machine scheduling with family setups to minimize total earliness and tardiness

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize total earliness and tardiness when family setup times exist. The paper proposes optimal branch-and-bound algorithms for both the group technology assumption and if the group technology assumption is removed. A heuristic algorithm is proposed to solve larger problems with the group technology assumption removed. The proposed algorithms were empirically evaluated on problems of various sizes and parameters. The paper also explores how the choice of procedure affects total earliness and tardiness if an implementation of lean production methods has resulted in a reduction in setup times. An important finding of these empirical investigations is that scheduling jobs by removing the group technology assumption can significantly reduce total earliness and tardiness.     

Common due window size and location determination in a single machine scheduling problem

We consider a single machine static and deterministic scheduling problem in which jobs have a common due window. Jobs completed within the window incur no penalties, other jobs incur either earliness or tardiness penalties. The objective is to find the optimal size and location of the window as well as an optimal sequence to minimise a cost function based on earliness, tardiness, window size, and window location. We propose an O(n log n) algorithm to solve the problem.     

Variable neighborhood search for minimum cost berth allocation

The berth allocation problem is to allocate space along the quayside to incoming ships at a container terminal in order to minimize some objective function. We consider minimization of total costs for waiting and handling as well as earliness or tardiness of completion, for all ships. We assume ships can arrive at any given time, i.e., before or after the berths become available. The resulting problem, which subsumes several previous ones, is expressed as a linear mixed 0–1 program. As it turns out to be too time-consuming for exact solution of instances of realistic size, a Variable Neighborhood Search (VNS) heuristic is proposed, and compared with Multi-Start (MS), a Genetic Search algorithm (GA) and a Memetic Search algorithm (MA). VNS provides optimal solutions for all instances solved to optimality in a previous paper of the first two authors and outperforms MS, MA and GA on large instances.     

Meta-heuristic approaches for minimizing total earliness and tardiness penalties of single-machine scheduling with a common due date

This study addresses a class of single-machine scheduling problems involving a common due date where the objective is to minimize the total job earliness and tardiness penalties. A genetic algorithm (GA) approach and a simulated annealing (SA) approach utilizing a greedy local search and three well-known properties in the area of common due date scheduling are developed. The developed algorithms enable the starting time of the first job not at zero and were tested using a set of benchmark problems. From the viewpoints of solution quality and computational expenses, the proposed approaches are efficient and effective for problems involving different numbers of jobs, as well as different processing time, and earliness and tardiness penalties.     

On scheduling around large restrictive common due windows

This paper deals with the problem of scheduling a number of jobs on a single machine around a large, restrictive common due window. We consider individual earliness and tardiness penalties for the jobs. The objective is to find an optimal schedule which jointly minimizes the sum of the earliness and tardiness penalties. This problem is intractable and hence no efficient procedure for solving large instances is expected to be found. For this reason we first introduced a mapping of the problem which takes advantage of the structural properties inherent to optimal solutions. Secondly we solved the problem under study by using this mapping and applying three meta-heuristics, namely evolutionary strategy, simulated annealing and threshold accepting. To validate the quality of these approaches, altogether 250 benchmark problems with different window sizes and positions of up to 200 jobs are examined. Furthermore small instances are solved to optimality by a mixed integer programming formulation.     

Determination of common due window location in a single machine scheduling problem

We consider the static deterministic single machine scheduling problem in which all jobs have a common due window. Jobs that are completed within the window incur no penalty. The objective is to find the optimal sequence and the optimal common due window location given that the due window size is a problem parameter such that the weighted sum of earliness, tardiness, and due window location penalties is minimized. We propose an O(n log n) algorithm to solve the problem. We also consider two special cases for which simple solutions can be obtained.     

Parallel machine scheduling with common due windows

With the prevalence of on-time scheduling, timely product submission has become a crucial contributor to customer satisfaction. Studies examining on-time scheduling primarily seek to determine the minimum weighted sum of earliness and tardiness penalties. This study assumes that all machines are identical. Furthermore, this study assumes that jobs are independent and share a common due date window when investigating scheduling problems involving parallel machines with a minimum total number of early and tardy jobs (or maximum number of on-time jobs). This study presents related theorems and a novel simplified algorithm based on the problem. Additionally, rule characteristics are examined, and simulated data are used to verify the effectiveness and timeliness of the proposed algorithm. The theoretical proof and data test results all indicate that the proposed approach obtains the best solution within the shortest time.