假定给定任务集合$S=\{a_1,a_2,\cdots,a_n\}$，其中任务$a_i$在启动后需要$p_i$个时间单位完成。你有一台计算机来运行这些任务，每个时刻只能运行一个任务。令$c_i$表示任务$a_i$的完成时间，即任务$a_i$被执行完的时间。你的目标是最小化平均完成时间，即最小化$(1/n)\sum_{i=1}^{n}c_i$。例如，假定有两个任务$a_1$和$a_2$，$p_1 = 3$，$p_2 = 5$，如果$a_2$首先运行，然后运行$a_1$，则$c_2 = 5$，$c_1 = 8$，平均完成时间为$(5+8)/2=6.5$。如果$a_1$先于$a_2$执行，则$c_1 = 3$，$c_2 = 8$，平均完成时间为$(3+8)/2 = 5.5$。
a. 设计算法，求平均完成时间最小的调度方案。任务的执行都是非抢占的，即一旦$a_i$开始运行，它就持续运行$p_i$个时间单位。证明你的算法能最小化平均完成时间，并分析算法的运行时间。
b. 现在假定任务并不是在任意时刻都可以开始执行，每个任务都有一个释放时间$r_i$，在此时间之后才可以开始。此外假定任务执行是可以抢占的 (preemption)，这样任务可以被挂起，稍后再重新开始。例如，一个任务$a_i$的运行时间为$p_i = 6$，释放时间为$r_i = 1$，它可能在时刻1开始运行，在时刻4被抢占。然后在时刻10恢复运行，在时刻11再次被强占，最后在时刻13恢复运行，在时刻15运行完毕。任务$a_i$共运行了6个时间单位，但运行时间被分割成三个部分。在此情况下，$a_i$的完成时间为15.设计算法，对此问题求解平均时间最小的调度方案。证明你的算法确实能最小化完成时间，分析算法的运行时间。
Answer:
a. 算法设计如下：按照运行时间从小到大的顺序依次运行每个任务，算法的时间复杂度为排序时间$O(n\lg n)$。下证该算法能最小化平均完成时间：
首先假设算法最后得到的任务序列为$\{i_1,i_2,\cdots,i_n\}$，取一个最优序列$\{j_1,j_2,\cdots,j_n\}$。假设存在一个$r$，使得两个序列的前$r$项相同，第$r+1$项相同。那么我们能够得到如下推论：

用时最短的任务。我们使用$p^i_k$来表示算法得到的任务序列的第$k$个任务用时；$p^j_k$来表示算法得到的任务序列的第$k$个任务用时；使用$P^i_k$来表示算法序列的第$k$个任务的完成时间；使用$P^j_k$来表示最优序列的第$k$个任务的完成时间。
两种序列的前$r$个任务的完成时间之和相同，设第$r$个任务的完成时间为$A$。那么最优序列的剩余$n-r$个任务的完成时间之和为：

$\sum_{d = r+1}^{n}P^j_d = \sum_{d = r+1}^{n}\left(A + \sum_{e = r+1}^{d}p^j_e\right)$

由于$i_{r+1} \ne j_{r+1}$，故存在$j_k = i_{r+1}\quad(r+1 < k \le n)$，不妨交换最优序列中的$j_{r+1}$和$j_k$。此时最优序列剩余的$n-r$个任务的完成时间之和为：

$\sum_{d = r+1}^{n}\hat{P}^j_d = \sum_{d = r+1}^{n}\left(A + \sum_{e = r+1}^{d}p^j_e\right) + (n-r)(p^j_k - p^j_{r+1}) + (n-k+1)(p^j_{r+1} - p^j_k)$
有$p^j_k \le p^j_{r+1}$以及$r+1 < k \le n$，故：

$\sum_{d = r+1}^{n}\hat{P}^j_d = \sum_{d = r+1}^{n}P^j_d + (k-r-1)(p^j_k - p^j_{r+1}) \le \sum_{d = r+1}^{n}P^j_d$
这说明交换后的新序列的平均完成时间小于等于最优序列的平均完成时间，这与最优序列的假设相矛盾，故此处的小于等于只能取等于号，即$p^j_k = p^j_{r+1}$，此时交换两个任务不会使平均完成时间发生变化，因此该最优序列可以保持最优序列的性质。

根据上一条推论，我们可以知道对于任意前$r\quad (r < n)$项相同的一组算法生成的序列和一组最优序列，都可以通过交换操作在保持最优序列性质的前提下，使得两个序列的第$r+1$位也相同，直到两个序列完全相同。故该算法能最小化平均完成时间。

b. 采用最短用时优先算法：优先执行当前剩余时间最短的可执行任务。
首先假设算法最后得到的每个时刻所执行的任务的任务序列为$\{i_1,i_2,\cdots,i_m\}$，取一个最优序列$\{j_1,j_2,\cdots,j_m\}$，此处$m$为所有任务的总用时。假设该最优序列能满足在所有其他的最优序列中拥有一个最大的$r$，使得两个序列的前$r$项不相同，第$r+1$项相同。那么我们能够得到如下推论：

对于指代不同任务的$i_{r+1}$和$j_{r+1}$，由算法定义可知任务$T^i_{r+1}$的剩余用时小于等于任务$T^j_{r+1}$的剩余用时。若相等，则将后续序列中所有的$i_{r+1}$和$j_{r+1}$互换，该操作不影响最优序列的性质，并使最优序列的前$r+1$项与算法提供的序列前$r+1$项相同，这与最大$r$的假设相矛盾。因此任务$T^i_{r+1}$的剩余用时必然小于任务$T^j_{r+1}$的剩余用时。
已知算法优先执行当前剩余时间最少的任务，记两个序列当前完成的任务为$R$个，则第$R+1$个任务的完成时间必然是算法序列的完成时间更小。此处记算法序列第$r+1$个时刻执行的任务为$T^i$，记最优序列第$r+1$个时刻执行的任务为$T^j$。那么两个任务在第$r+1$个时刻前各自都还有剩余用时，记$T^i$的剩余用时为$t^i$；$T^j$的剩余用时为$t^j$，特别地，有$t^i < t^j$。根据上述内容，我们知道在最优序列从第$r+2$个时刻起的后续的$m-r-1$个时刻里，任务$T^i$还要执行$t^i$次，而任务$T^j$还要执行$t^j-1$次。
我们将最优序列中自第$r+1$个时刻起的所有执行任务$T^j$的$t^j$个时刻记为一个集合$U\quad(|U| = t^j > t^i)$，以及所有执行任务$T^i$的时刻即为一个集合$V$，将两个集合合并记做$W = U + V$。则$W$中有$t^i+t^j$个元素，我们使时刻最小的前$t^i$个时刻在最优序列中都执行任务$T^i$，剩余的后$t^j$个时刻在最优序列中执行任务$T^j$。已知原先任务$T^i$与任务$T^j$的完成时间分别为$F^i = MAX_{k \in [1,t^i]}\left(u_k|u_k \in U\right)$和$F_j = MAX_{k \in [1,t^j]}\left(u_k|u_k \in V\right)$。同时，两者之和也可以表示为：

$Q = F^i + F^j = MAX\left(F^i,F^j\right) + MIN\left(F^i,F^j\right)$

那么交换后的新序列中，除了任务$T^i$与任务$T^j$，其他任务的完成时间完全不变，而任务$T^i$的完成时间变为$W$中第$t^i$大的时刻，记为$w_{t^i},\quad w_{t^i} < MIN\left(F^i,F^j\right)$。而任务$T^j$的完成时间变为$MAX\left(F^i,F^j\right)$，故交换后的两者之和：

$Q' = w_{t^i} + MAX\left(F^i,F^j\right) < MAX\left(F^i,F^j\right) + MIN\left(F^i,F^j\right) = Q$
故在其他任务的完成时间都不变的情况下，交换后的这两个任务的完成时间之和变小了，这与原序列为最优序列的假设不相符。故假设不成立，不存在这样的最大$r$使得前$r$项相同，第$r+1$项不同。即所有项都相同。故该算法能够获取最小平均完成时间。

上一篇文章讲了最小二乘算法的原理。这篇文章通过一个简单的例子来看如何通过Python实现最小乘法的线性回归模型的参数估计。
王松桂老师《线性统计模型——线性回归与方差分析》一书中例3.1.3。
说的是一个实验容器靠蒸汽供应热量，使其保持恒温，通过一段时间观测，得到下图表中的这样一组数据：
蒸汽-环境温度数据其中，自变量X表示容器周围空气单位时间的平均温度(℃)，Y表示单位时间内消耗的蒸汽量(L)，共观测了25个单位时间(表中序号一列)。
那么，我们要怎样对这组数据进行线性回归分析呢？一般分三步：(1)画散点图，找模型；(2)进行回归模型的参数估计；(3)检验前面分析得到的经验模型是否合适。
画散点图
创建一个DataTemp的文件夹，在其中分别创建"data"、"demo"文件夹用于存放数据文件、Python程序文件。
把前面图中的数据导入Excel中，命名为：“蒸汽供应.xlsx”，用来作为数据源。
数据导入Excel后创建Python文件：”leastsquare.py“。在文件头加入utf-8编码的说明以支持中文字符，然后添加必要的注释。
# -*- coding: utf-8 -*-"""Created on Fri Mar 20 14:07:41 2020@author: gao"""import必要的第三方库。
"""第三方库"""importpandasaspdimportmatplotlib.pyplotaspltfromscipy.optimizeimportleastsqimportnumpyasnp使用下面的代码将Excel数据读入Python Pandas DataFrame中。
"""把excel中的数据读入datafram"""filePath=u'../data/蒸汽供应.xlsx'#含中文字符，前面加u表示用Unicode 格式进行编码data=pd.read_excel(filePath,index_col=u'序号')提取其中的Y、X列并绘制散点图
Xi=data[u'X']Yi=data[u'Y']"""画散点图"""plt.figure()plt.scatter(Xi,Yi,color='red',label='sample data',linewidth=2)plt.legend(loc='lower right')plt.show()散点图结果如下：
散点图从图中看出大致服从一个线性分布，所以我们采用一元线性回归模型来进行分析。
回归模型的参数估计
一元线性模型的一般公式为
一元线性回归模型我们使用最小二乘法估算出α、β即可求出经验回归方程。
经验模型Python中对一元线性模型的参数进行参数估计是很简单的，如下代码所示：
deffun(p,x):#回归模型函数k,b=preturnk*x+bdeferror(p,x,y):#误差returnfun(p,x)-yp0=np.array([1,3])para=leastsq(error,p0,args=(Xi,Yi))k,b=para[0]上面代码的关键之处有三点：
(1)定义模型函数、误差函数。其中误差函数error，实际上就是我们模型的估计值与实际的观察值之差，我们就是通过这个差值的最小二乘来对模型中的参数进行估计的。也就是说，前面的经验模型的参数取不同的值，那对于xi可以求出不同的yi，这个yi是我们估计值和实际的观测值进行求差就是估计误差，参数取值不同估计误差不同，我们要找到一组参数使得对于所有的观测值的误差的平方和最小。
(2)调用scipy的leastsq函数时，需要有误差函数、初始参数作为输入，还需要把我们读到的观测数据作为参数传入leastsq函数，这是此函数的三个关键的输入参数。
(3)leastsq的返回参数是多个，所以放到一个元组(tuple)中，返回tuple类型para的第一个元素para[0]是一个nupy.ndarray类型，存放的即是满足最小二乘规则的估计参数。
经验模型的效果
可以使用下面的代码打印经过最小二乘运算后的经验模型。
"""打印结果"""print('y='+str(round(k,2))+'x+'+str(round(b,2)))最后一步工作就是把我们的经验模型的线画到前面的散点图上，看一下模型的效果。
"""绘制结果曲线"""x=np.linspace(20,80,2)y=k*x+b"""画散点图"""plt.figure()plt.scatter(Xi,Yi,color='red',label='sample data',linewidth=2)plt.plot(x,y,color='blue',label='result line')plt.legend(loc='lower right')plt.show()绘出的结果图像如下：
模型结果曲线当然，我们还可以通过判定系数来看一下我们的回归方程与数据拟合的效果好坏，这个在后续的文章中再说。

	

上一篇文章讲了最小二乘算法的原理。这篇文章通过一个简单的例子来看如何通过Python实现最小乘法的线性回归模型的参数估计。
王松桂老师《线性统计模型——线性回归与方差分析》一书中例3.1.3。
说的是一个实验容器靠蒸汽供应热量，使其保持恒温，通过一段时间观测，得到下图表中的这样一组数据：
其中，自变量X表示容器周围空气单位时间的平均温度(℃)，Y表示单位时间内消耗的蒸汽量(L)，共观测了25个单位时间(表中序号一列)。
那么，我们要怎样对这组数据进行线性回归分析呢？一般分三步：(1)画散点图，找模型；(2)进行回归模型的参数估计；(3)检验前面分析得到的经验模型是否合适。
画散点图
创建一个DataTemp的文件夹，在其中分别创建"data"、"demo"文件夹用于存放数据文件、Python程序文件。
把前面图中的数据导入Excel中，命名为：“蒸汽供应.xlsx”，用来作为数据源。
创建Python文件：”leastsquare.py“。在文件头加入utf-8编码的说明以支持中文字符，然后添加必要的注释。
# -*- coding: utf-8 -*-
"""Created on Fri Mar 20 14:07:41 2020@author: gao"""
import必要的第三方库。
"""第三方库"""
import pandas as pd
import matplotlib.pyplot as plt
from scipy.optimize import leastsq
import numpy as np
使用下面的代码将Excel数据读入Python Pandas DataFrame中。
"""把excel中的数据读入datafram"""
filePath = u'../data/蒸汽供应.xlsx'  #含中文字符，前面加u表示用Unicode 格式进行编码
data = pd.read_excel(filePath, index_col=u'序号')
提取其中的Y、X列并绘制散点图
Xi = data[u'X']
Yi = data[u'Y']
"""画散点图"""
plt.figure()
plt.scatter(Xi, Yi, color='red', label='sample data',linewidth=2)
plt.legend(loc='lower right')
plt.show()
散点图结果如下：
从图中看出大致服从一个线性分布，所以我们采用一元线性回归模型来进行分析。
回归模型的参数估计
一元线性模型的一般公式为
我们使用最小二乘法估算出α、β即可求出经验回归方程。
Python中对一元线性模型的参数进行参数估计是很简单的，如下代码所示：
def fun(p,x): #回归模型函数
k,b = p
return k*x+b

def error(p,x,y): #误差
return fun(p,x)-y

p0 = np.array([1,3])
para = leastsq(error,p0,args=(Xi,Yi))

k,b = para[0]
上面代码的关键之处有三点：
(1)定义模型函数、误差函数。其中误差函数error，实际上就是我们模型的估计值与实际的观察值之差，我们就是通过这个差值的最小二乘来对模型中的参数进行估计的。也就是说，前面的经验模型的参数取不同的值，那对于xi可以求出不同的yi，这个yi是我们估计值和实际的观测值进行求差就是估计误差，参数取值不同估计误差不同，我们要找到一组参数使得对于所有的观测值的误差的平方和最小。
(2)调用scipy的leastsq函数时，需要有误差函数、初始参数作为输入，还需要把我们读到的观测数据作为参数传入leastsq函数，这是此函数的三个关键的输入参数。
(3)leastsq的返回参数是多个，所以放到一个元组(tuple)中，返回tuple类型para的第一个元素para[0]是一个nupy.ndarray类型，存放的即是满足最小二乘规则的估计参数。
经验模型的效果
可以使用下面的代码打印经过最小二乘运算后的经验模型。
"""打印结果"""
print('y='+str(round(k,2)) + 'x+' +str(round(b,2)))
最后一步工作就是把我们的经验模型的线画到前面的散点图上，看一下模型的效果。
"""绘制结果曲线"""
x=np.linspace(20,80,2)
y=k*x+b

"""画散点图"""
plt.figure()
plt.scatter(Xi, Yi, color='red', label='sample data',linewidth=2)
plt.plot(x,y,color='blue',label='result line')
plt.legend(loc='lower right')
plt.show()
绘出的结果图像如下：
当然，我们还可以通过判定系数来看一下我们的回归方程与数据拟合的效果好坏，这个在后续的文章中再说。

上一篇文章讲了最小二乘算法的原理。这篇文章通过一个简单的例子来看如何通过Python实现最小乘法的线性回归模型的参数估计。
王松桂老师《线性统计模型——线性回归与方差分析》一书中例3.1.3。
说的是一个实验容器靠蒸汽供应热量，使其保持恒温，通过一段时间观测，得到下图表中的这样一组数据：蒸汽-环境温度数据
其中，自变量X表示容器周围空气单位时间的平均温度(℃)，Y表示单位时间内消耗的蒸汽量(L)，共观测了25个单位时间(表中序号一列)。
那么，我们要怎样对这组数据进行线性回归分析呢？一般分三步：(1)画散点图，找模型；(2)进行回归模型的参数估计；(3)检验前面分析得到的经验模型是否合适。
画散点图
创建一个DataTemp的文件夹，在其中分别创建"data"、"demo"文件夹用于存放数据文件、Python程序文件。
把前面图中的数据导入Excel中，命名为：“蒸汽供应.xlsx”，用来作为数据源。数据导入Excel后
创建Python文件：”leastsquare.py“。在文件头加入utf-8编码的说明以支持中文字符，然后添加必要的注释。
# -*- coding: utf-8 -*-
"""Created on Fri Mar 20 14:07:41 2020@author: gao"""
import必要的第三方库。
"""第三方库"""
import pandas as pd
import matplotlib.pyplot as plt
from scipy.optimize import leastsq
import numpy as np
使用下面的代码将Excel数据读入Python Pandas DataFrame中。
"""把excel中的数据读入datafram"""
filePath = u'../data/蒸汽供应.xlsx'  #含中文字符，前面加u表示用Unicode 格式进行编码
data = pd.read_excel(filePath, index_col=u'序号')
提取其中的Y、X列并绘制散点图
Xi = data[u'X']
Yi = data[u'Y']
"""画散点图"""
plt.figure()
plt.scatter(Xi, Yi, color='red', label='sample data',linewidth=2)
plt.legend(loc='lower right')
plt.show()
散点图结果如下：散点图
从图中看出大致服从一个线性分布，所以我们采用一元线性回归模型来进行分析。
回归模型的参数估计
一元线性模型的一般公式为一元线性回归模型
我们使用最小二乘法估算出α、β即可求出经验回归方程。经验模型
Python中对一元线性模型的参数进行参数估计是很简单的，如下代码所示：
def fun(p,x): #回归模型函数
k,b = p
return k*x+b
def error(p,x,y): #误差
return fun(p,x)-y
p0 = np.array([1,3])
para = leastsq(error,p0,args=(Xi,Yi))
k,b = para[0]
上面代码的关键之处有三点：
(1)定义模型函数、误差函数。其中误差函数error，实际上就是我们模型的估计值与实际的观察值之差，我们就是通过这个差值的最小二乘来对模型中的参数进行估计的。也就是说，前面的经验模型的参数取不同的值，那对于xi可以求出不同的yi，这个yi是我们估计值和实际的观测值进行求差就是估计误差，参数取值不同估计误差不同，我们要找到一组参数使得对于所有的观测值的误差的平方和最小。
(2)调用scipy的leastsq函数时，需要有误差函数、初始参数作为输入，还需要把我们读到的观测数据作为参数传入leastsq函数，这是此函数的三个关键的输入参数。
(3)leastsq的返回参数是多个，所以放到一个元组(tuple)中，返回tuple类型para的第一个元素para[0]是一个nupy.ndarray类型，存放的即是满足最小二乘规则的估计参数。
经验模型的效果
可以使用下面的代码打印经过最小二乘运算后的经验模型。
"""打印结果"""
print('y='+str(round(k,2)) + 'x+' +str(round(b,2)))
最后一步工作就是把我们的经验模型的线画到前面的散点图上，看一下模型的效果。
"""绘制结果曲线"""
x=np.linspace(20,80,2)
y=k*x+b
"""画散点图"""
plt.figure()
plt.scatter(Xi, Yi, color='red', label='sample data',linewidth=2)
plt.plot(x,y,color='blue',label='result line')
plt.legend(loc='lower right')
plt.show()
绘出的结果图像如下：模型结果曲线
当然，我们还可以通过判定系数来看一下我们的回归方程与数据拟合的效果好坏，这个在后续的文章中再说。