《物流配送在线调度(精)/排序与调度丛书》介绍了物流配送在线调度的基本理论方法，并结合几类实际的物流配送在线调度问题的在线解决方案对这些理论和方法进行介绍和说明。

第1章 物流配送基本问题
1.1 物流配送概述
1.1.1 配送的概念
1.1.2 配送的作用
1.1.3 配送与运输的区别
1.1.4 配送的分类
1.2 物流配送的作业流程
1.2.1 配送的基本环节
1.2.2 货物分拣
1.2.3 车辆配载
1.2.4 配送线路选择
1.3 物流配送调度概述
1.3.1 物流配送车辆调度问题的构成要素
1.3.2 物流配送车辆调度问题分类
1.3.3 物流配送车辆调度问题的现有求解方法
第2章 物流配送在线调度问题
2.1 在线调度问题
2.1.1 单台机器在线调度
2.1.2 平行机在线调度
2.1.3 按时在线调度
2.1.4 分批在线调度
2.1.5 自由作业在线调度
2.2 在线问题与竞争策略理论的发展简史
2.3 基本概念
2.4 基本方法
2.5 应用领域
2.6 小结
第3章 物流配送在线调度决策方法
3.1 引言
3.2 涉及决策环境时的决策问题的分类及定义
3.2.1 传统决策问题的解决方法
3.2.2 确定型决策问题的决策方法
3.2.3 风险型决策问题的特征和决策方法
3.2.4 不确定型决策问题的决策方法
3.3 不确定型决策问题的传统解决方法的缺陷
3.4 在线决策理论的基本概念
3.5 竞争策略解决在线决策问题的研究框架
3.6 基本方法
3.6.1 最坏情形均衡法
3.6.2 应用实例
3.7 小结
第4章 成对需求的k服务器调度问题
4.1 问题的提出
4.2 预备知识
4.2.1 离线问题的最优策略
4.2.2 工作函数策略
4.3 度量空间具有k+2个顶点的情形
4.4 竞争比的下界
4.5 小结
第5章 k卡车调度问题
5.1 问题描述
5.2 离线k卡车调度问题的解法
5.2.1 动态规划法求解
5.2.2 最大流最小费用求解
5.3 竞争比的一个下界
5.4 竞争策略和竞争比
5.4.1 复位策略
5.4.2 局部贪婪策略
5.4.3 两种在线竞争策略的比较
5.5 深度在线k卡车调度问题
5.6 小结
第6章 具有时间窗口的k卡车运输问题
6.1 引言
6.2 模型及预备知识
6.3 有关的研究结果
6.4 两个简单的在线竞争策略
6.5 睡眠策略
6.6 开放式OLTTP的竞争比的下界
6.7 开放式OLTTP的竞争策略
6.7.1 RS竞争比的结果
6.7.2 LOS竞争比的结果
6.8 小结
第7章 在线Mobile Agent调度问题
7.1 引言
7.2 Mobile Agent计算模型
7.3 多Agent系统的结构
7.4 OTSP的竞争策略
7.4.1 一般谐和策略
7.4.2 GHS的竞争比
7.4.3 竞争比的下界
7.4.4 一个特例
7.5 试验结果及参数分析
7.5.1 实验结果
7.5.2 参数分析
7.6 小结
第8章 总结与展望
8.1 总结
8.2 展望
参考文献
索引
附录A 英汉排序与调度词汇

丛书序言我知道排序问题是从20世纪50年代出版的一
本书名为OperationsResearch（可能是1957年出版）的书
开始的。书中讲到了Johnson的同顺序两台机器的排序问题
并给出了解法。Johnson的这一结果给了我深刻的印象。第
一，这个问题是从实际生活中来的。第二，这个问题有一
定的难度，Johnson给出了完整的解答。第三，这个问题显
然包含着许多可能的推广，因此蕴含了广阔的前景。在
1960年左右，我在《英国运筹学（季刊）》（当时这是一
份带有科普性质的刊物）上看到一篇文章，内容谈到三台
机器的排序问题，但只涉及四个工件如何排序。这篇文章
虽然很简单，但从中我也受到一些启发。我写了一篇讲稿
，在中国科学院数学与系统科学研究所里做了一次通俗报
告。之后我就到安徽参加“四清”工作。不意所里将这份
报告打印出来并寄了几份给我。我寄了一份给华罗庚教授
。他对这方面的研究表现出很大的支持。这是20世纪60年
代前期的事，接下来便开始了文化大革命，倏忽十年。20
世纪70年代初我从“五七”干校回京，发现国外在排序问
题方面已做了不少工作，并曾在1966年开了一次国际排序
问题会议，出版了一本论文集TheoryofScheduling。我与
韩继业教授一道共同做了一些工作，也算得上是排序问题
在我国的一个开始。想不到在秦裕瑗、林诒勋、唐国春以
及许多教授的努力下，随着国际的潮流，排序问题的理论
和应用在我国得到了如此蓬勃的发展，真是可喜可贺！
众所周知，在计算机如此普及的今天，一门数学分支
的发展必须与生产实际相结合，才称得上走上健康的道路
。一种复杂的工具从设计到生产，一项巨大复杂的工程从
开始施工到完工后的处理，无不牵扯到排序问题。因此，
我认为排序理论的发展是没有止境的。我很少看小说，但
近来我对一本名叫《约翰·克里斯托夫》的作品很感兴趣
。这是罗曼·罗兰写的一本名著，实际上它是以贝多芬为
背景的一本传记体小说。这里面提到贝多芬的祖父和父亲
都是宫廷乐队指挥，当他的父亲发现他在音乐方面是个天
才的时候，便想将他培养成一个优秀的钢琴师，让他到各
处去表演，可以名利双收，所以强迫他勤学苦练。但贝多
芬非常反感，他认为这样的作品显示不出人的气质。由于
贝多芬的如此感受，他才能谱出如《英雄交响乐》《第九
交响乐》等深具人性的伟大诗篇（乐章）。我想数学也是
一样。只有在人类生产中体现它的威力的时候，才能显示
出数学这门学科的光辉，也才能显示出我们作为一个数学
家的骄傲。任何一门学科，尤其是一门与生产实际有密切
联系的学科，在其发展初期，那些引发它成长的问题必然
是相互分离的，甚至是互不相干的。但只要它继续向前发
展，一些问题便会综合趋于统一，处理问题的方法也会发
展壮大、深入细致，所谓根深叶茂、蔚然成林。我们的这
套丛书现在有数册正在撰写之中，主题纷呈，蔚为壮观。
相信在不久以后会有不少新的著作出现，使我们的学科呈
现一片欣欣向荣、繁花似锦的局面，则是鄙人所厚望于诸
君者矣。
越民义
中国科学院数学与系统科学研究院
2019年4月
序言
随着信息化技术的高速发展，近年来物流配送在线调
度问题已成为一个热点议题，本书将对这一问题展开论述
。本书前3章重点阐述了物流配送在线调度决策问题以及竞
争策略的理论，从第4章开始，基于著名的k服务器问题
，首先提出了多需求的k服务器调度问题，并对该问题的
一些特例进行了分析和解决。第5章讨论了在线k服务器
问题的另外一个变形——在线k卡车问题。第6章提出并
讨论了在线k卡车运输问题
（onlinektrucktransportationproblem，OLTTP）
，并给出了该问题的竞争策略和相应的竞争比的一些初步
的研究成果。第7章讨论了在国际互联网上MobileAgent的
在线调度问题，即如何优化MobileAgent的远程决策系统
的反应时间的问题，并通过系统分析以及仿真结果证实了
本书所提出的MobileAgent的网络计算方法的可行性和效
果。第8章对全书进行总结并对在线决策理论的应用前景进
行了展望。具体逻辑框架图如图01所示。
图01本书逻辑框架图
全书具体内容组织如下：第1章简要介绍了物流配送的
基本问题。第2章用较多的篇幅对物流配送在线调度问题及
其竞争策略理论中的一些重要的内容进行了较详细的论述
，它们是今后几章的研究工作赖以进行的基础。最后说明
了全文的组织和结构。第3章首先介绍了经典的决策理论在
涉及决策环境时的分类方法以及在此种分类下的各种决策
问题定义、决策方法以及解的特点。特别论述了在涉及不
确定性问题时传统决策的理论、方法以及它们无法克服的
缺陷。然后结合传统的决策理论和计算机科学领域的在线
问题和竞争策略理论，建立其在线决策理论的理论体系。
其中包括在线决策理论的基本概念、基本方法以及应用竞
争策略进行在线决策问题研究的基本框架。第4章基于著名
的k服务器问题，首先提出了多需求的k服务器调度问
题。它

第3章物流配送在线调度决策方法
本章首先介绍了经典的决策理论在涉及决策环境时的分类方法以及在此种分类下的各种决策问题定义、决策方法以及解的特点。特别论述了在涉及不确定性问题时传统决策的理论、方法以及它们在物流配送在线调度中无法克服的缺陷。然后将结合传统的决策理论和计算机科学领域的在线问题和竞争策略理论，建立其在线决策理论的理论体系，其中包括在线决策理论的基本概念、基本方法以及应用在线决策理论进行研究的基本框架。
3。1引言
决策是人们在政治、经济、技术和日常生活中普遍存在的一种选择方案的行为。决策是管理中经常发生的一种活动。决策就是决定的意思。在人们的日常生活中，在企业、公司的经营活动中，在国家的政治活动中，在战争爆发时的军事活动中，以及在各个领域的科研活动中，经常需要我们做决定。决策的正确与否会给个人、企业、国家带来收益或者损失。人们日常生活中的决策活动中，一个错误决策可能导致一盘棋的一败涂地，也可能导致一个家庭的分崩离析。而一个企业的决策失误，例如新产品的试制中的决策失误，则可能带来几十万乃至数百万的损失。与此相比，政治活动中国家的决策失误所带来的损失则有时是无法用金钱来衡量的，严重时可能会给国家和人民带来巨大的灾难。我国建设三峡大坝的决策过程经历了几十年，数以万计的各个领域的专家参与了决策论证，国家政府在此决策问题的慎重态度从另外一个侧面反映了这种牵扯国计民生的决策问题是不允许哪怕一点点失误的。同样的道理，在军事活动中，指挥员的决策失误不仅会导致战斗的失败，而且有可能会因为这种失败牺牲掉许多战士的生命。在一切失误中，决策失误是最大的失误。正所谓，一招不慎，满盘皆输！
关于决策的重要性，诺贝尔奖获得者西蒙有一句名言“管理就是决策”。这句话的意思是说管理的核心就是决策。决策是一种选择行为。最简单的是回答“是”与“否”的决策问题，例如选择进入某个市场还是不进入、开发某个新产品还是不开发、囚犯是招供还是不招供等。比较复杂的是回答“选择哪一个”的决策问题，例如运送货物是走陆路、水路还是空路？周末夫妻是去看足球、看时装表演还是待在家里什么也不做，等等。更为复杂的是需要回答“怎么样”的决策问题。例如，图论中的最短路问题、结点的遍历问题等。研究决策的学问，并将现代科学技术成就应用于决策，称为决策学。决策学包括的内容非常广泛，如决策心理学、决策的数量化方法、决策的评价以及决策支持系统、决策自动化等。
3。2涉及决策环境时的决策问题的分类及定义
传统决策理论对于决策问题的分类有各种各样的方法，其中按照决策者所处的决策环境来划分可以分为以下三种类型。
确定型决策问题。决策环境是完全确定的，作出选择的结果也是确定的。或者说确定型决策是指那些未来状态完全可以预测，有精确、可靠的数据资料支持的决策问题。如计划经济体制下的产品包销，原料统一调拨以及许多传统的运筹和优化领域的决策模型都属于这类决策问题。
风险型决策问题。决策的环境是不完全确定的，但是相关事件的发生概率是已知的。从而，该类决策问题的解属于概率意义上的期望结果。这类决策问题往往具有多种未来状态和相应的后果，虽然得不到这些状态和相应后果的完全充分、可靠、确定的信息，但是可以获得各种状态发生的概率。如引入市场经济体制后的产品开发的决策问题，石油勘探公司对于是否进行钻井的决策等。
不确定型决策问题。决策环境是决策者对于相关的决策变量的信息是完全未知的，甚至对于有关事件发生的概率也是一无所知，只能凭借决策者的主观倾向进行决策。即此类问题不仅难以获得各种状态发生的概率，而且甚至对未来状态都难以把握。例如开发尚未经过用户考验的全新产品往往属于这类决策问题。
3。2。1传统决策问题的解决方法
决策方法是决策学研究的重要组成部分。上面简要介绍了传统的决策理论在涉及决策环境时的问题分类和各类问题的定义。下面简要介绍各类问题的决策方法，着重介绍有关不确定型决策问题的内容，同时为了本书的整体性和可读性，也简要介绍其他类问题的内容。
3。2。2确定型决策问题的决策方法
根据确定型决策问题的定义，我们知道确定型决策者面对的决策状态是确定的，决策问题的结构也是比较清楚的，这样决策者就可以利用决策因素和决策结果之间的数量关系建立数学模型，并运用数学模型进行决策。确定型决策问题的决策方法很多，例如运筹学中常用的一些方法，线性规划、非线性规划、动态规划等。
3。2。3风险型决策问题的特征和决策方法
同样，根据风险型决策问题的表述我们可以总结出该类决策问题的一些基本特征如下：（1）存在着多种选择方案。（2）存在着不以决策者的意志为转移的两种以上的客观状态。（3）不同选择方案在不同的客观状态下的损失和收益是可以计算出来的。（4）未来将出现某种