极小化完工时间和的有界批调度问题

考虑m台并行批加工同型机上n个带有释放时间的工件的调度问题,目标是极小化完工时间和.给出了一个多项时间近似方案.     

集装箱码头桥机调度问题基于完工时间下界的算法

关注单船桥机调度问题,指出了单船桥机的闲置会影响码头整体的运作效率。以单个集装箱为任务单位,考虑桥机移动时间、安全距离等约束,建立了最小化桥机完工时间和闲置时间的多目标规划模型。基于完工时间下界的两种不同情况：以重点贝位工作量确定和以平均工作量确定,分别设计了基于邻域搜索的启发式算法和基于贪心策略的“分割贝位”算法,并且证明了在以平均工作量确定下界的情况中该算法不会导致桥机闲置。不同规模、不同下界类型的算例表明：提出的模型与算法得到的桥机调度计划更适合实际生产作业,能够有效地逼近完工时间下界,算法运行速度较现有的研究有显著的提高。     

集装箱码头桥机调度问题基于完工时间下界的算法

关注单船桥机调度问题,指出了单船桥机的闲置会影响码头整体的运作效率。以单个集装箱为任务单位,考虑桥机移动时间、安全距离等约束,建立了最小化桥机完工时间和闲置时间的多目标规划模型。基于完工时间下界的两种不同情况:以重点贝位工作量确定和以平均工作量确定,分别设计了基于邻域搜索的启发式算法和基于贪心策略的"分割贝位"算法,并且证明了在以平均工作量确定下界的情况中该算法不会导致桥机闲置。不同规模、不同下界类型的算例表明:提出的模型与算法得到的桥机调度计划更适合实际生产作业,能够有效地逼近完工时间下界,算法运行速度较现有的研究有显著的提高。     

一类复杂约束下的并行机重调度问题研究

研究一类从实际指挥和保障系统提炼的考虑机器多发故障、且具有工件释放时间、机器可用时间、以及机器适用限制等约束的并行同速机重调度问题.首先,建立同时考虑效率、安全和稳定性的混合整数规划重调度模型,该模型利用最大完工时间和总完工时间来度量效率,用重调度前后分配不同机器的工件总数来度量安全性和稳定性;其次,考虑到该问题的NP-hard性和实际调度对机器故障快速响应的要求,提出基于优先规则和右移重调度策略混合的重调度算法框架;最后,将所提重调度算法框架应用于实际案例,分析比较不同优先规则和右移重调度策略组合的求解效果.结果表明,与工件释放时间相关的优先准则与右移重调度策略结合具有较好的优化效果.值得一提的是,文章首次研究具有多重约束的并行机重调度问题(Pm|r_j,a_j,M_j,brkdwn|C_(max),TC,ND).     

恶化率与工件无关的线性加工时间调度问题

讨论恶化率与工件无关的线性加工时间调度问题 .对于工件间具有平行链约束 ,目标函数为极小化最大完工时间的单机问题 ,分别就链不允许中断和链允许中断两种情况给出了最优算法 .对于工件间没有优先约束 ,目标函数为极小化完工时间和的平行机问题 ,证明了工件按基本加工时间不减排列可以得到最优调度 .     

并行分批排序综述

并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。     

具有指数和位置学习效应的机器排序问题

本文考虑指数学习效应和位置学习效应同时发生的新的排序模型.工件的实际加工时间不仅依赖于已经加工过工件正常加工时间之和的指数函数,而且依赖于该工件所在的位置.单机排序情形下,对于最大完工时间和总完工时间最小化问题给出多项式时间算法.此外某些特殊情况下,总权完工时间和最大延迟最小化问题也给出了多项时间算法.流水机排序情形,对最大完工时间和总完工时间最小化问题在某些特殊情形下给出多项时间算法.     

考虑加工速率相互干扰的平行机调度最优策略研究

随着智能互联网的应用深入、个性化消费时代的来临,制造服务企业开始注重利用网络平台为客户提供个性化的定制服务,在此过程中派生出了产品设计师可与多名客户在线同步交互的一种新型服务模式。本文根据设计师服务效率受并行服务客户数量影响的特征,将问题刻画为机器处理速度相互影响的一类平行机调度模型,以最小化总完工时间为优化目标,研究设计最优调度方案。首先,对于只有两名设计师且各自同时处理最多两个任务的情形,提出了改进的SPT调度规则,运用归纳法证明了该规则可以生成最优加工方案。其次,对改进的SPT规则进行任务分配方式的适当松驰以便更加易于操作,并证明松驰后的新分配方案保持了解的最优性。最后,将相关结论推广至多名设计师的一般情形。上述研究为个性化在线定制服务模式下的有效调度策略制定提供了良好的理论支撑。     

加工时间可控单机加权总完工时间Pareto优化研究

针对单机环境最优化加权总完工时间问题,当工件加工时间可通过分配资源进行压缩时,研究对工件的加工次序和时间压缩量的优化,从而权衡调度性能目标和资源成本目标。调度性能目标为压缩后工件的加权总完工时间,资源成本目标为工件压缩量的线性函数。此问题复杂性已被证明为NP-hard,为弥补较少有研究从Pareto优化角度求解该问题有效前沿的不足,针对经典NSGA-II求解时易早熟收敛的特点,采用算法混合方式进行优化方法研究。融合归档式多目标模拟退火算法跳出局部极值的优势,启用外部存档策略提升种群的多样性,采用主从模式的并行结构提升求解效率。最后为检验优化方法的有效性,一方面通过对Benchmark测试函数ZDT1-6的求解,表明混合算法对不同结构和形状目标函数兼具普适性和有效性;另一方面结合问题特点设计有效编码方式,针对随机生成算例进行求解。通过分析有效前沿收敛性和多样性,验证了所提方法对于优化加工时间可控单机加权总完工时间问题的有效性。     

考虑成本的最大延迟时间同类机调度问题

假定生产时机器成本是固定的,研究了一类考虑成本的同类机调度问题,调度的目标是在给定加工完所有作业的总预算的成本限制下最小化最大作业延迟时间。为该类问题构建了混合整数规划模型。通过设计相关规则在机器成本预算内来选择加工机器,以及对传统的LPT(最长加工时间优先)、ECT(最早完工时间优先)、EDD(最早工期优先)等算法进行改进,提出了一个启发式算法H,并理论证明了该算法在同型机和同类机下的最坏误差界。通过算例说明了算法的执行情况,同时也考虑了给定总预算不同的多种情形,采用大量随机数据实验验证了算法的有效性。     

A genetic algorithm for flow shop scheduling problems

Many scheduling problems are NP-hard problems. For such NP-hard combinatorial optimization problems, heuristics play a major role in searching for near-optimal solutions. In this paper we develop a genetic algorithm-based heuristic for the flow shop scheduling problem with makespan as the criterion. The performance of the algorithm is compared with the established NEH algorithm. Computational experience indicates that genetic algorithms can be good techniques for flowshop scheduling problems.     

Approximations and auctions for scheduling batches on related machines

We consider the scheduling of groups of identical jobs on related machines with sequence independent setup times. We provide a 2-approximation algorithm for minimizing the makespan. The second result is a truthful, polynomial time, randomized mechanism for the batch scheduling problem with a deterministic approximation guarantee of 4.     

An iterative algorithm for scheduling UET tasks with due dates and release times

A new polynomial-time iterative algorithm is presented for the scheduling problem with a unit execution time task system, parallel identical processors, precedence constraints, release times, and the criterion of maximum lateness. For the maximum lateness and makespan problems the algorithm allows to achieve the performance guarantees previously known only for the problems without release times.     

Randomized On-Line Scheduling Similar Jobs to Minimize Makespan on Two Identical Processors

In this paper we consider an on-line scheduling problem, where jobs with similar processing times within [1, r] arrive one by one to be scheduled in an on-line setting on two identical parallel processors without preemption. The objective is to nlinimize makespan. We devise a randomized on-line algorithm for this problem along with a lower bound.     

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 machine scheduling problems with a single server

In this paper, we consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the schedule length (makespan), as well as the forced idle time. The makespan problem is known to be NP-hard even for the case of two identical parallel machines. This paper presents a pseudopolynomial algorithm for the case of two machines when all setup times are equal to one. We also show that the more general problem with an arbitrary number of machines is unary NP-hard and analyze some list scheduling heuristics for this problem. The problem of minimizing the forced idle time is known to be unary NP-hard for the case of two machines and arbitrary setup and processing times. We prove unary NP-hardness of this problem even for the case of constant setup times. Moreover, some polynomially solvable cases are given.     

Project Scheduling with Multiple Modes: A Genetic Algorithm

In this paper we consider the resource-constrained project scheduling problem with multiple execution modes for each activity and makespan minimization as objective. We present a new genetic algorithm approach to solve this problem. The genetic encoding is based on a precedence feasible list of activities and a mode assignment. After defining the related crossover, mutation, and selection operators, we describe a local search extension which is employed to improve the schedules found by the basic genetic algorithm. Finally, we present the results of our thorough computational study. We determine the best among several different variants of our genetic algorithm and compare it to four other heuristics that have recently been proposed in the literature. The results that have been obtained using a standard set of instances show that the new genetic algorithm outperforms the other heuristic procedures with regard to a lower average deviation from the optimal makespan.     

Flow-shop scheduling with a learning effect

The paper is devoted to some flow-shop scheduling problems with a learning effect. The objective is to minimize one of the two regular performance criteria, namely, makespan and total flowtime. A heuristic algorithm with worst-case bound m for each criteria is given, where m is the number of machines. Furthermore, a polynomial algorithm is proposed for both of the special cases: identical processing time on each machine and an increasing series of dominating machines. An example is also constructed to show that the classical Johnson's rule is not the optimal solution for the two-machine flow-shop scheduling to minimize makespan with a learning effect. Some extensions of the problem are also shown.     

Scheduling under a Non-renewable Resource Constraint

This paper examines a single-machine, non-renewable-resource-constrained scheduling problem where jobs have arbitrary processing times and resource requirements. Unit supply of a resource is assumed at each time period. Performance criterion is makespan. It is proved that this problem is identical to the two-machine flowshop problem, enabling the use of Johnson's algorithm. Immediate extensions of this result are presented.     

考虑返修的建设项目时间-成本-质量问题

当施工过程中质量不达标需要返修以改进项目质量,但相应地会影响项目工期和成本。本文基于经典多模式资源受限项目调度问题构建一种新的非线性规划模型,目标为项目成本最小和工期最短,其中项目成本考虑返修成本以提高项目质量。首先,使用二元非独立正态分布函数描述活动质量,根据活动间的串联或并联关系定义隐蔽工程质量为活动质量的函数。其次,本文提出一种基于NSGA的混合蛙跳算法,采用串行进度产生方案和调整的活动列表编码,其中蛙跳过程结合了遗传算法中的交叉操作和基于置换的局域搜索。最后,整个模型算法应用于框架铁路立交桥施工项目,验证本文算法性能在支配解数量和质量上都优于标准NSGA。