一类有动态时间窗的并行多机启发式调度算法

航班过站服务中的货邮装卸作业调度是一类有时间窗和作业调整时间的多目标多设备并行作业动态排序问题，其特点是作业时间窗和服务作业时间动态变化。在分析区别于一般制造业生产作业排序特点的基础上，建立了服务作业的调度模型．提出了设备能力差的概念．给出一个考虑不同设备加工能力的启发式分配法。当时间窗或服务时间发生变化时，算法只需要修改判断矩阵中的一行或一列数据，而对算法运行的效率没有影响。算例分析显示，能力差分配算法在减少航班延误数量、时间压设备生产能力平衡上均优于目前使用的先到先服务和最小负荷调度的混合算法。     

A CLASS OF GENERALIZED MULTIPROCESSOR SCHEDULING PROBLEMS

1. IntroductionOne of the fundamental problems in the theory of scheduling is to sChedule n independent jobs non-preemptively on m 2 2 multiprocessors. It is well-known that PllCm.. andPI I Z:=, wiCi are strongly NP-hardll'2].In this paper, we consider a class of generalized multiprocessor scheduling problem. It canbe described as follows: There are m almost identical processors M = {MI, M2,'' 5 Mm}, andn independent jobs J = {JI, J2,'' 9 Jn}. The processing time of job Ji is pi. A…     

M/M/N可修排队稳态分布存在条件的一种新形式

利用母函数方法研究有一个修理工且服务台忙时与闲时故障率不同的M/M/N可修排队,得到系统的一些可靠性指标和系统稳态分布存在条件的一种新形式.     

Scheduling jobs with general learning functions

This paper deals with single-machine scheduling problems with a more general learning effect based on sum-of-processing-time. In this study, sum-of-processing-time-based learning effect means that the processing time of a job is defined by a decreasing function of the total normal processing time of jobs that come before it in the sequence. Results show that even with the introduction of the sum-of-processing-time-based learning effect to job processing times, single-machine makespan minimization problems remain polynomially solvable. The curves of the optimal schedule of a total completion time minimization problem are V-shaped with respect to job normal processing times.     

考虑等待时间的网约车与出租车均衡定价研究

针对网约车和出租车的出行服务竞争,用等待时间刻画影响需求的服务质量,考虑网约车服务质量高于/低于出租车服务质量两种情景,探讨两种服务共存的条件及均衡定价策略.研究结果表明:当总网络外部性为正时,两种服务需较高差异化才能实现共存;而当总网络外部性为负时,无需其他条件约束,两种服务皆可共存.通过算例分析,分析了网约车服务等待时间对消费者剩余的影响以及参数对两种服务共存条件的影响.此外,借鉴参照依赖理论描述出租车司机在竞争市场中的获利感知,提出基于服务质量差异的网约车管制措施.研究结论为网约车服务定价和监管策略提供了一定的管理启示.     

具有优势机器和恶化工件的流水作业排序问题

针对流水作业排序问题,建立了具有优势机器和恶化工件并且有无空闲限制的排序模型.在该排序模型中,机器加工工件时,工件的相邻加工工序之间不允许出现空闲,工件的加工时间是其开工时间的严格增加线性函数.其中讨论的优势机器有2种情况:机器形成增减增优势关系和机器形成减增减优势关系.考虑了多台机器的流水作业排序问题,其中,目标函数分别为极小化最大完工时间和极小化总完工时间,对于这两类问题分别给出了求解最优排序的多项式算法和它们的计算复杂性,并通过证明证实了算法的有效性.     

The M/M/1 queue with working vacations and vacation interruptions

In this paper, we study the M/M/1 queue with working vacations and vacation interruptions. The working vacation is introduced recently, during which the server can still provide service on the original ongoing work at a lower rate. Meanwhile, we introduce a new policy：, the server can come back from the vacation to the normal working level once some indices of the system, such as the number of customers, achieve a certain value in the vacation period. The server may come back from the vacation without completing the vacation. Such policy is called vacation interruption. We connect the above mentioned two policies and assume that if there are customers in the system after a service completion during the vacation period, the server will come back to the normal working level. In terms of the quasi birth and death process and matrix-geometric solution method, we obtain the distributions and the stochastic decomposition structures for the number of customers and the waiting time and provide some indices of systems.     

带有资源消耗的加权总完工时间单机排序问题

讨论了带有资源消耗的加权总完工时间单机排序问题,其加工时间是资源量的线性函数,目标函数是完工时间和消耗资源量的加权总和。由于该问题是NP 难问题,所以给出了一个非常有效的局部搜索算法及其算法复杂性和一个算例。利用有关资源分配的性质分别对单位资源分配量的消耗相等、工件的权因子相等、工件的资源分配上限相等和单位资源分配量的消耗相等、工件的权因子相等、工件的正常加工时间相等两种特殊情况给出了最优算法。     

工件带有温降的生产与前运输协调调度问题

研究单机环境下生产与生产前运输的协调调度问题,目标函数是最大完成时间最小化.具有热状态的工件等待加工时温度降低会导致处理时间的增加,从而假设具有热状态工件的实际处理时间为等待时间与初始处理时间之和,温度无变化工件的处理时间不变.对于车辆数为1,被调度工件均温度不变化问题,给出最优算法;证明了车辆数为1,同时存在热状态工件和温度不变化工件的调度问题和车辆数为2,同时存在热状态工件的调度问题是强NP困难问题.     

多工件族无缓冲混合Flow Shop问题的模型和算法构建

旨在研究并解决一类从集装箱混合装卸作业环境中提取的多工件族无缓冲混合Flow Shop问题. 针对该问题的多工件族、无缓冲、部分专用机、与机器和顺序相关的准备时间和作业时间等特点, 构建了问题的混合整数线性规划模型. 鉴于问题的NP-hard特性, 构造型的启发式算法被构建, 核心思想是基于提出的机器库存和配额等概念, 动态构建含有三元副的调度列表, 三元副表示与其一一对应的工件在3阶混合Flow Shop中的加工轨迹. 通过仿真实验、下界分析, 发现算法能获得好的近优解和低的计算成本. 更为重要的是, 算法尤其适合解决大规模的实际问题.     

线性减少加工时间的资源约束单机排序问题

讨论具有连续资源的单机排序问题。在这一模型中,工件的准备时间是所消耗资源的非负严格减少连续函数,工件的加工时间是开工时间的严格减少线性函数。考虑两类问题,第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量。第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间。对两类问题讨论了最优排序的某些特征。基于对问题的分析,分别给出了求解最优资源分配的方法。结果表明,加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立。     

N个不同部件串联而成的M/G/1可修排队系统

考虑服务台由N个不同部件串联而成的M/G/1可修排队系统,其中服务台正常当且仅当N个部件都正常.在假定每个部件的寿命服从指数分布,而故障部件的修理时间服从一般分布下,通过引入服务台的"广义忙期",提出了分析服务台有关可靠性指标的一种新方法,用该方法更加简洁的讨论了服务台的许多感性趣的可靠性指标,得到了一些重要的可靠性结果,推广了已有的结论.     

一类资源约束单机排序问题

讨论具有连续资源的单机排序问题．在这一模型中，工件的释放时间是所消耗资源的非负严格减少连续函数，工件的加工时间是开工时间的严格增加线性函数．考虑两类问题，第一类问题的目标函数是在满足最大完工时间限制条件下极小化资源消耗总量、第二类问题的目标函数是在满足资源消耗总量限制条件下极小化最大完工时间．对两类问题讨论了最优排序的某些特征．基于对问题的分析，分别给出了求解最优资源分配的方法．结果表明，加工时间为常数情况的结论对于加工时间是开工时间线性函数的情况仍然成立。     

交货期服从指数分布的单机随机调度问题

工件完成时间与交货期差的绝对值加权和最小化单机随机调度问题是JIT（just-in-time)生产环境下的典型调度模型，是NP－hard问题，然而，当工件权值与加工时间成正比时，LPT（largest processing time）工件调度是问题的最优解，讨论了该问题加工时间和交货期都为随机变量，其中交货期服从指数分布，且工件权值与加工时间成正比的情形，给出了问题的最优解，并在一定条件下将结果推广到机器随机故障的情形。     

基于改进DP算法的具有优先序的变速机最小化成本调度

研究了工件具有任意标准优先序、一台机器在同一时间只可加工一个工件、最小化工件加工成本与机器使用成本之和的变速机调度问题.为该问题建立了DP模型,通过启发式规则和常规动态规划方法相结合、引入工件完工时间界限并保存每一步函数值,得到改进的DP算法,数值实验显示该算法具有较强的寻优能力和稳定性.     

基于最短时间碎片的在线生产调度算法研究

针对订单型企业的在线生产调度问题,文章通过统计每个设备上允许插入工序的时间区间,提出了基于最短时间碎片的启发式在线生产调度算法.该算法的主要思路是将工序的先后约束关系和在同一设备上的先后执行关系统一建模为无圈有向图,从而依据最短时间碎片将新订单的调度过程转化为在有向图中添加顶点和有向边的过程.仿真实验结果表明该算法可以在保证订单交付期的前提下实现排产任务,并尽可能少地变更已排产工序在设备上的相对位置;在订单频繁到达时,调度的设备利用率较高,达到了约94%;此外,算法运行较快,适用于较大规模在线生产调度问题的求解.     

Optimal design for a retrial queueing system with state-dependent service rate

This paper considers a single server retrial queue in which a state-dependent service policy is adopted to control the service rate. Customers arrive in the system according to a Poisson process and the service times and inter-retrial times are all exponentially distributed. If the number of customers in orbit is equal to or less than a certain threshold, the service rate is set in a low value and it also can be switched to a high value once this number exceeds the threshold. The stationary distribution and two performance measures are obtained through the partial generating functions. It is shown that this state-dependent service policy degenerates into a classic retrial queueing system without control policy under some conditions. In order to achieve the social optimal strategies, a new reward-cost function is established and the global numerical solutions, obtained by Canonical Particle Swarm Optimization algorithm, demonstrate that the managers can get more benefits if applying this state-dependent service policy compared with the classic model.     

一种物料需求计划进货批量决策技术

进货批量的选择是物料需求计划(MRP)系统中一项重要的工作,现有的MRP物料批量的计算方法主要有:配套批量法、固定周期法、EOQ法、期间平衡法等;然而,这些进货批量决策技术只是进货总费用最小化的一种近似计算。针对该情况,提出了一种MRP进货批量决策技术并把这种技术和以上的技术做了充分的对比分析。     

SCHEDULING TWO GROUPS OF JOBS WITH INCOMPLETE INFORMATION

In real world situations, most scheduling problems occur neither as complete off-line nor ascomplete on-line models. Most likely a problem arises as an on-line model with some partialinformation. In this article, we consider such a model. We study the scheduling problem P(n_1,n_2),where two groups of jobs are to be scheduled. The first job group is available beforehand. As soon asall jobs in the first group are assigned, the second job group appears. The objective is to minimize thelongest job completion time(makespan). We show a lower bound of 3/2 even for very special cases.Best possible algorithms are presented for a number of cases. Furthermore, a heuristic is proposed forthe general case. The main contribution of this paper is to discuss the impact of the quantity ofavailable information in designing an on-line algorithm. It is interesting to note that the absence ofeven a little bit information may significantly affect the performance of an algorithm.     

Internet-based event synchronization communication driven telerobotics

1.INTRODUCTION Teleoperationmakeshumansensetoremotesiteand byitmanyapplicationcanbeappliedintoreality.A longdistanceteleoperationmayhavemuchmore meaningtopeople.Throughspace,sea,andnet work,teleoperationshowsitscharm.Whenrobotis inducedinteleoperationastheexecutoritisnamedas telerobotics.NowInternetisprevalentintheworld,overitconstructingateleroboticshasmuchmoread vantagethanothers,likeconstructingeasily,cheap costandmaintenanceconvenientlyetc.Butthereare alsosomedrawbacksinit,liketimede…