整数规划（精彩4篇）

【前言导读】这篇优秀范文“整数规划（精彩4篇）”由阿拉题库网友为您精心整理分享，供您学习参考之用，希望这篇资料对您有所帮助，喜欢就复制下载吧！

整数规划【第一篇】

整数规划是一类要求问题中的全部或一部分变量为整数的数学规划。如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。在数学规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求结果必须是整数。本文采用整数规划的方法建立排课问题的数学模型，优化高等院校的排课。

1.排课问题描述

排课问题要素

从本校的实际情况来看，排课主要考虑时间、班级、课程、教室和教师这五个要素。对这些要素进行透彻的分析以及适当的预处理，是建立排课模型的基础。

（1）时间：排课问题中涉及的时间概念有学年、学期、周、天、时间段等。结合本校上课时间安排，只考虑按周来组织课表。每周5天教学日，每天10节课，分5个时间段，每2节课为一个时间段，每学期每周课表固定。

（2）课程：每门课程都有自己的编号、名称、学时和学分等要求，每门课程每周需要安排的学时体现为课程的学分，1学分的概念就是在每个教学周安排1个学时；周学时为奇数的课程，排课时的实际周学时，取为比该课程周学时数大的最小偶数。

（3）教室：每个教室要有自己的编号和类别名称（如普通教室、多媒体教室、微机室等）等，每个教室在同一时间只能上一门课，且满足教室的类型和教室的容量等要求。

（4）班级：每个班级要有自己的编号和名称，在同一时间一个班级只能上一门课程。

（5）教师：每个教师要有自己的工号和名称，在同一时间一个教师只能上一门课程。

排课问题约束条件

因为排课问题要满足多种约束条件，为了降低问题复杂度，可将排课的约束条件按照程度分为两大类：硬性约束和软性约束。前者是排课问题中必须遵循的原则，是衡量排课方案是否切实可行的标准，后者是排课过程中应当予以考虑，不一定必须满足，但如果满足可使排课结果更加合理，是衡量排课方案优劣的标准。

2.排课数学模型的建立

基于排课问题涉及的要素和约束条件建立如下排课问题的数学模型，主要对排课问题进行严格的数量关系描述。

模型参数

3.结论

虽然我们给出了排课问题的目标方程。但是，在不同的教学环境和不同的评价人的主观因素下，很难确定各个目标方程的权重。所以，对于课表优劣的衡量仍然是一个模糊的概念。基于以上的情况，我们不需要寻找问题的最优解，而应该寻找满足约束条件（F，C，L，R，T）的较优组合，从中选择一个作为较优课表。后续我们将进一步研究求解整数规划问题的算法，使排课达到最优组合。

参考文献

[1]鄂强金。基于混沌遗传算法的排课问题研究[硕士学位论文].哈尔滨工程大学，2009.

[2] of some mathematical model of scheduling theory[D].Moscow University，1980.

[3]于艳东。基于遗传模拟退火算法的智能组卷系统研究[硕士学位论文].内蒙古大学，2011.

[4]C c Construction of Class-Teacher

整数规划【第二篇】

关键词：仓库；选址；混合整数规划法

伴随着经济的发展，我国零售业诞生了许多不同形式的连锁零售业态，同时，也将零售业市场推到白热化竞争状态。如今，连锁零售业的竞争已由店前发展到店后，变成物流配送体系的竞争。而在物流体系中，仓库作为衔接供应链上下游的环节，起到了至关重要的作用，所有的物流活动几乎都是围绕它来进行。合理的仓库选址可以有效地节省企业经营的各项费用，保证物流系统的高效运作。因此，通过合理的优化算法来选择仓库地址具有十分重要的意义和应用价值。

一、广西南宁市A便利店有限公司仓库选址现状

1.公司现状简介

广西南宁市A便利店有限公司是一家从事商业贸易、连锁管理、信息咨询及相关培训业务的连锁企业，公司以特许加盟连锁方式发展分店，至今旗下拥有二十多家便利门店，其中公司直营12家。公司各门店分布如图1：

2.公司仓库现状分析

便利店在选址时，一般选择在居民区和办公区的要道，以为居民提供便利为宗旨。所以，公司能否保证店面的持续供货是发展的关键因素。为了满足各门店商品需求，企业仓库选址一般优先选择在可以辐射到各个门店的地方。

广西南宁市A便利店有限公司目前在南宁市建政路租有一个仓库（如图1绿色标注所示），仓库为企业老板之前租住的公寓套房改用而成，供旗下12家门店的货物配送。仓库地处一个居民小区内，面积为70平米的一房一厅套房，仓库内布局混乱，没有作业功能区域划分，仓库的设备设施相对落后，仓库货物不分区存储，储存物品品种繁多，单品种货量存储少，货物堆放凌乱。

公司目前配送分为单双期配送，将12家门店按所在区域不同划分为两条路线配送，其操作流程为：首先，各门店店长依据销售情况按公司要求在规定的配送日前一天通过系统向仓库发送商品需求信息；其次，仓库接到信息，整理信息，汇总各门店订货数量，再根据仓库库存量分拣各门店的商品数量；最后，次日下午联系司机安排货物配送。若门店错过发送商品信息时间，便只能等待下一个配送日配送，或者商品量很大的情况下单独配送，或者门店自行到仓库提货。部分门店经常出现缺货现象。

3.公司仓库选址存在的问题

（1）随意性较强

在仓库选址前，公司没有综合的考虑门店的日均货物需求量、门店的分布情况等因素，选择较为轻率，仅凭公司领导的感觉，将仓库设立在自身周围闲余的空间内，将其仅仅当作一个单纯的收发货地，尚未认识到其真正的存在价值。

（2）租金成本较高

仓库建设费用为仓库选址主要考虑的因素之一，在满足仓库需求的情况下应该尽量选择建设费用低的地段。A公司将仓库选择在居民住宅小区内，租金成本偏高。

（3）交通便捷性较差

在连锁企业的物流体系中，每天具有出入库、交货等交通的压力，交通条件对物流的配送效率具有重要的影响，交通的不便将直接影响车辆配送的效率，从而导致门店的缺货。A公司仓库所在路段来往车辆频繁，路况严重拥堵，货车只能在规定的时间段通行，对门店需求的及时配送以及供应商对其的货物配送具有一定的影响。

（4）作业便捷性较差

仓库作为企业物流运作体系中的枢纽，每天都得处理大批量的货物，因此，需要给货物的存储、装卸搬运以及配送车辆停靠留有空余的空间。仓库地处居民小区内，货车的经常出入o周边居民带来诸多不便。

（5）扩展性差

连锁便利店仓库不仅要满足当下各门店供货需求，还应满足连锁店扩张的需要，即要求仓库要有好的扩展性。A便利店有限公司仓库处于居民小区楼内，面积小，仅为70平米，储存物品品种繁多，单品种货量存储少，难以满足各门店的供货需求，周边没有空置房源，仓库没有扩展空间，不能满足门店供货扩张的需求。这些都制约着A公司的经济效益的提升，长远来看，将成为阻碍公司发展的重要因素之一。

公司现有的仓储设施的不足将影响其为各门店提供优质的服务，重新规划企业仓库的选址变得尤为重要，合理的仓库选址对于提高门店服务水平和经济增长有着重要的意义。

二、混合整数规划法选址模型建立

通过对连锁便利店仓库的业务和数据分析可知，其物流配送一般具有以下特点：商品品种繁多、单店商品需求量小、物流配送频率高、配送点多且散、配送时间快等。鉴于以上特点，连锁便利店企业仓库辐射范围小，其通常和需求点的距离较近，其服务主要是能及时满足各个便利门店的供货需求。因此，这类仓库在选址时，不仅仅只考虑物流成本的降低，还得考虑是否能及时为其服务的各个门店提供服务。本文只针对考虑企业仓库到需求点的单因素配送情况进行分析，这过程涉及的影响因素主要考虑从仓库到门店的运输费用和仓库固定建设费用两个部分以及配送时间的长短。

为了寻求合适A便利店有限公司仓库的地址，笔者通过调查分析，综合考虑了四个层面：（1）门店的分布状况，门店的分布区域是选址的重要因素之一，选址应尽量靠近门店一些，特别是在门店比较集中的地方设置仓库；（2）配送服务条件及成本，依据门店供货时间要求，计算从仓库到门店的距离和时间，保证配送及时，满足门店货源需求，为顾客提供及时便捷的服务，同时保证配送成本的控制；（3）仓库租金费用，同一地区不同地段房源各不相同，租金也不一样，此外，还得考虑周边是否留有未来发展的空间；（4）交通条件，一方面在选址时要充分考虑周边的交通运输条件的便利性，以提高配送效率，缩短配送运输时间，另一方面还要考虑仓库与周边交通条件的协调性，因为连锁便利店仓库每天输送货物的频率较大，对周边的交通道路会有一定的影响。最终选取了3个备选地址，为了在这3个备选地中选出最合适的地址作为公司的仓库地址，收集了一些相关的数据，对3个备选地和目前仓库做一个定量比较分析，希望从中选出一个合适的地址。

1.问题描述

广西南宁市A便利店有限公司，旗下设有12个连锁门店（如图1红色标注所示），用j1-j12表示，其坐标及门店日需求量（将各种不同的商品均转化为重量来记）如下表1所示。1个现有仓库（如图1绿色标注所示）、3个仓库备选点（如图1蓝色标注所示），分别用i1-i4表示，其坐标及现有仓库和备选仓库的固定投资费用如下表2所示。单位产品从仓库到门店的运价因为都在市内，单位运价均为1，各门店到仓库备选点的距离（根据谷歌地图驾车路线实际距离为准）如表3，各门店到仓库备选点的配送时间如表4（配送时间=距离/速度，假设车辆行驶速度为35km/h）。要求在备选仓库中选择一个仓库，在能够及时满足所有门店需求的前提下，使得总费用最小以及所用时间最小。

（3）符号说明

与上一模型相同的字母表示相同的意义

L――供应商的数量；

Wki――从供应商k到仓库i的运输量；

Ak――供应商k的供应量；

Cki――单位产品从供应商k到仓库i的配送费用；

gi――仓库i单位流转量的管理费用；

Tki――供应商k到仓库i的配送时间；

Tij――仓库i到门店j的配送时间。

（4）模型解释

式（1）表示供应商到仓库到门店的运输成本和固定建设成本之和最小；

式（2）表示供应商到仓库到各门店配送的时间之和最小；

式（3）表示从供应商k向仓库提供的产品量不能超过其自身的供应能力；

式（4）表示仓库配送出的产品量与其从供应商的进货量相等；

式（5）表示所有需求点的需求都能得到满足；

式（6）表示仓库i向外配送的物资总量不能超过其自身容量；

式（7）规定了仓库建设数量的上限。

3.计算求解

将企业数据代入上式通过计算可知，选择目前的仓库i1的总成本为元，配送所需时间之和为；备选地i2的总成本为元，配送所需时间之和为；备选地i3的总成本为元，配送所需时间之和为；备选地i4的总成本为元，配送所需时间之和为。

4.广西南宁市A便利店有限公司仓库选址方案

根据计算比较分析，选择备选地i3作为公司仓库的情况下总成本最小，为元，配送花费时间也是最少，为。所以理论上i3为几个选择点中的最佳点。公司可以考虑将仓库搬到i3点处。

三、优化方案评价

现有仓库i1与三个备选地i2、i3、i4几个方面比较分析如下：

1.交通便利方面：i1处于路段拥堵地段；i2较为偏远，路况不算拥挤；i3、i4均处于大道附近，路况车辆不算拥挤，四周交通网较好。

2.仓库容量方面：i1面积太小，货物容纳量小，商品周转速度快，供应商配送次数频繁，配送成本较高；i2、i3、i4面积较大，货物容量较多，可满足门店货物的需求量。

3.与门店网络的距离情况：i1与各门店的距离较为集中，i2、i3、i4与各门店的距离较为分散。

4.成本方面：i1处于较中心地段，仓库租金成本偏高，i2、i3、i4处于较偏地段，租金成本相对较低。

连锁便利店的物流配送具有商品品种多、批量小、配送频率高、配送网点分散、适时快速配送等特点，这些特点要求企业必须有一个合理的仓库作为后盾。综合以上各方面因素分析，i3是A公司仓库最佳的选址点。

四、结论

仓库是连接连锁企业总部和各个门店的商品业务纽带，在连锁企业中起着承上启下的作用。所以在企业物流系统分析中，仓库选址是核心内容，仓库合理的选址能够减少运输成本，降低营运成本，从而提高利润。同时，合理的配送仓库可以使企业物流系统有效运转，为企业提供优质服务。

参考文献：

[1]皱德玲，倪晓峰。连锁零售企业配送中心选址研究[J].2010.

[2]蒋利军，蒋明，赵正佳。配送中心选址问题研究文献综述[J].物流科技期刊，2011.

整数规划【第三篇】

关键词：粒子群算法；0-1整数规划问题；背包问题；遗传算法；变异

中图分类号：文献标识码：A

Solving 0-1 Integer Programming Problem by Hybrid Particle Swarm Optimization Algorithm

XUE Feng，CHEN Gang, GAO Shang

(School of Computer Science and Engineering, Jiangsu University of Science and Technology, Zhenjiang 212003,China)

Abstract:The classical particle swarm optimization is a powerful method to find the minimum of a numerical function, on a continuous definition domain. The particle swarm optimization algorithm combine the ideal of the genetic algorithm is recommended to solve 0-1 integer programming problem. All the 6 hybrid particle swarm optimization algorithms are proved effective. Especially the hybrid particle swarm optimization algorithm with across strategy A and mutation strategy C is a simple and effective better algorithm than others. It can easily be modified for any combinatorial problem for which we have no good specialized algorithm.

Key words:particle swarm algorithm; 0-1 integer programming problem；knapsack problem; genetic algorithm; mutation

1 引 言

0-1整数规划问题是运筹学中一个典型的组合优化难题，有着广泛的应用背景，如货物装载问题，选址问题等。由于此问题比较简单典型，因此评价算法优劣常常以此问题作为的测试对象进行研究。0-1整数规划问题属于NP问题，目前求解的方法有精确方法（如动态规划、递归法、回溯法、分支限界法等［1］），近似算法（如贪心法［1］，Lagrange法等）以及智能优化算法（如模拟退火算法［2］、遗传算法［2］、遗传退火进化算法［3］、蚁群算法［4, 5］）。精确方法虽然可以得到准确解，但时间复杂性与物品数目成指数关系。近似算法和智能优化算法虽然不一定得到准确解，但可得到比较有效解，并且时间复杂性比较低。笔者尝试采用粒子群优化算法解决此问题。

2 0-1整数规划问题数学模型

0-1整数规划问题的数学模型为

min f(x1,x2,…,xn),

(x1,x2,…,xn)≥0(i=1,2,…,m)(1)

xi = 0, 1(i = 0, 1, …, n)3 基本粒子群优化算法

粒子群优化 (PSO, particle swarm optimization) 算法是一种进化计算技术，最早是由Kennedy与Eberhart于1995年提出的［6］。源于对鸟群捕食的行为研究的PSO同遗传算法类似，是一种基于迭代的优化工具。系统初始化为一组随机解，通过迭代搜寻最优值。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域。目前已提出了多种PSO改进算法［6~9］，如自适应PSO算法、杂交PSO算法、协同PSO算法。笔者提出基于遗传算法思想的一种新的PSO算法来解决0-1整数规划问题。PSO是模拟鸟群的捕食行为，设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远，那么找到食物的最优策略是什么呢？最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟，称为“粒子”。所有的例子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己。一个是粒子本身所找到的最优解，称为个体极值pbest；另一个极值是整个种群目前找到的最优解，称为全局极值gbest，另外也可以不用整个种群而只是用其中一部分为粒子的邻居，那么在所有邻居中的极值就是局部值。

在找到这2个最优值时， 每个粒子根据如下的公式来更新自己的速度和新的位置：

xk+1= xk + vk+1(3)

其中：vk是粒子的速度向量；xk是当前粒子的位置；pbestk粒子本身所找到的最优解的位置；gbestk整个种群目前找到的最优解的位置；c0, c1, c2表示群体认知系数，c0一般取介于（0, 1）之间的随机数，c1, c2取（0, 2）之间的随机数。vk+1是vk，pbest

首先把原约束方程作为罚函数项加入到原目标中，变成无约束的优化问题，即

min T=f(x1,x2,…,xn)+

M∑mi=1min (0,gi(x1,x2,…,xn)2 (4)

其中M为一充分大的正数。

计算技术与自动化2011年3月

第30卷第1期薛 峰等：求解0-1整数规划的混合粒子群优化算法

0-1整数规划问题的解用向量X = (x1, x2, …, xn)T表示，粒子群算法的本质是利用个体极值信息和全局极值两个信息，来指导粒子下一步迭代位置。对于0-1整数规划问题，若按基本粒子群算法，其速度难于表达，故采用遗传算法［2］ 交叉操作的思想：式（1）中的c0vk项可以看作遗传算法的变异操作，式（1）中的c1(pbestk

项可以看作遗传算法的交叉操作，让当前解与个体极值和全局极值分别作交叉操作，产生的解为新的位置。交叉方法可以采用以下两种方法

1）交叉策略A：

（1）两串old1和old2交叉，在第二个串old2中随机选择一个交叉区域；

（2）将old1的相应的交叉区域由old2交叉区域代替。

例如两父串为

old1=1 0 0 1 0 1 1 1 1 0 0 1，

old2=0 1 1 0 1 0 1 0 1 1 0 0。

交叉区域为0 1 0 1 1，交叉后为

new1=1 0 0 1 0 0 1 0 1 1 0 1。

2）交叉策略B：

（1） 随机产生k个1到n的整数j1, j2, …, jk；

（2）将old1的j1, j2, …, jk的位置数值由old2相应的部分代替。

具体变异操作可以采用下面三种

1）变异策略A：

（1） 在解空间(x1, x2, …, xn)T中随机选择一块区域，如(xi, xi+1, …, xj)T；

（2） (xi, xi+1, …, xj)T

如原来解为1 0 0 1 0 1 1 11 0 01 ，随机产生区域为1 1 0 0，则变异操作后的解为

1 0 0 1 0 1 1 0 0 1 1 1。

2）变异策略B：

（1） 在解空间(x1, x2, …, xn)T中随机选择一块区域，如(xi, xi+1, …, xj)T；

（2）. (xi, xi+1, …, xj)T取随机值。

3）变异策略C：

（1） 在解空间(x1, x2, …, xn)T中随机选择一个1到n的整数j；

（2） xj

如原来解为1 0 0 1 0 1 1 1 1 0 0 1，随机产生整数为4，则变异操作后的解为1 0 0 0 0 1 1 1 1 0 0 1。

解0-1整数规划问题的混合粒子群算法hybrid _PSO如下：

1) 设定粒子数np，规定迭代次数nmax，随机产生np个初始解X0；

2) 根据当前位置根据式（4）计算适应值l0，设置当前适应值为个体极值plbest，当前位置为个体极值位置pxbest，根据各个粒子的个体极值plbest，找出全局极值glbest和全局极值位置gxbest；

3) While (迭代次数＜规定迭代次数n┆max) do

4) for j =1: np

5) 第j个粒子位置X0(j)与gxbest交叉得到X1

7) 对X1(j)进行变异操作；

8) 根据当前位置计算适应值l1；

9) 如果l1(j)＜ plbest (j)，则pxbest (j) = X1(j)，plbest (j) = l1(j)；

10) End

11) 根据各个粒子的个体极值plbest，找出全局极值glbest和全局极值位置gxbest；

12) X0

13) End

14) 输出全局极值glbest和全局极值位置xbest。

该粒子群算法的时间复杂性估算如下：以交叉时间和变异操作花费最多，变异操作的时间与交叉操作时间相近，里面循环需要作O(3np)交叉（或变异）操作，外循环执行n┆max次，所以时间复杂性大约为O(3npn┆max)。

5 数值仿真与分析

各种策略比较

背包问题是一个典型的0-1整数规划问题。采用文献［4］的一个典型的背包问题数据，n = 10，C = 269 g，{p1, p2, …, p10}={55，10，47，5，4，50，8，61，85，87}元，{c1, c2, …, c10}={95，4，60，32，23，72，80，62，65，46} g。混合粒子群算法分别2种交叉策略和3种变异策略，组合起来6种方法进行比较，各种算法各测试100次，最优目标值为295元，最优解为：X*= {0, 1, 1, 1, 0, 0, 0, 1, 1, 1}。参数粒子数np = 10，最大迭代次数nmax = 10的结果如表1所示；若粒子数np = 20，最大迭代次数n┆max = 30。蚁群算法参数如下：蚂蚁数20，信息素强度重要性

从表1和表2可以看出，只进行交叉操作的2个算法，效果比较差。效果最好的是交叉策略A和变异策略C的组合算法最好。并且交叉策略A比交叉策略B简单，变异策略C也比变异策略A和变异策略B简单。变异策略A和变异策略B，由于变异的位数多，增加了部分差的解，因此效果不如变异方法C。随着粒子数和最大迭代次数增加，计算效果变好，但其运算量也将增大。另外这里的交叉操作与遗传算法的交叉操作不同，遗传算法随机选择2个解进行交叉，而粒子群交叉操作是对每个粒子进行交叉操作，并且与个体极值和全局极值进行交叉，考虑了优生的思想，因此效果比传统的遗传效果好。

与其他算法比较

针对背包问题，对递归算法、回溯方法和蚁群算法进行了比较，采用文献［5］的测试方法，数据随机产生，各ci和pi在1~100随机生成，物品种类取值为5~20，背包的质量容量C为总质量的80 %。每个算法运行100次，统计出平均运行时间，结果如表3所示。从表3可以看出交叉策略A和变异策略C的粒子群算法运行的效率较高，尽管比文献［5］蚁群算法运行稍长点，但得到精确解的次数较高（表2）。

6 结 论

本文作者创新点：提出的粒子群优化算法不仅可以解决0-1整数规划问题，对于整数规划问题，对该算法作适当修改，也可适用。粒子群优化算法(PSO)是起源对简单社会系统的模拟，擅长连续问题的优化，笔者尝试采用粒子群算法解决离散优化问题。PSO研究处于初期，还有许多问题值得研究，如算法的收敛性、理论依据等。但从当前的粒子群算法的应用效果［8, 9］来看，这种模仿自然生物的新型系统的寻优思想无疑具有十分光明的前景，更深入的工作还有待于进一步展开。

参考文献

［1］ 王晓东。 计算机算法设计与分析［M］. 北京： 电子工业出版社， 2001：92-168

［2］ 王凌。 智能优化算法及其应用［M］. 北京： 清华大学出版社， 2001：17-59

［3］ 金慧敏，马良。 遗传退火进化算法在背包问题中的应用［J］. 上海理工大学学报，2004，26(6)： 561-564

［4］ 马良，王龙德。 背包问题的蚂蚁优化算法［J］. 计算机应用， 2001, 21(8): 4-5

［5］ 于永新，张新荣。 基于蚁群系统的多选择背包问题优化算法［J］. 计算机工程， 2003, 29(20)：75-76

［6］Eberhart R C，Kennedy J. A new optimizer using particles swarm theory ［A］. Proc Sixth International Symposium on Micro Machine and Human Science ［C］. Nagoya, Japan, 1995. 30~43

［7］ Shi Y H, Eberhart R C. A modified particle swarm optimizer ［A］. IEEE International Conference on Evolutionary Computation ［C］. Anchorage, Alaska, 1998：69-73

［8］ 李爱国， 覃征， 鲍复民， 等。 粒子群优化算法［J］.计算机工程与应用， 2002, 38(21)：1-3

［9］ 杨维，李歧强。 粒子群优化算法综述［J］. 中国工程科学， 2004, 6(5)：87-94.

整数规划【第四篇】

[关键词] 主生产计划 路径 整数规划 半导体制造

一、引言

本文主要致力于解决半导体后道封装测试厂的生产计划问题。基于客户确定的订单及销售预测的需求，我们来研究如何计算一个合适的数量的芯片在一个给定的周期内完成加工。工厂可以是自有工厂也可以考虑外发加工。订单完成率及产能约束会加入到约束条件之中。计算结果可以用于决策每个工厂的投料的数量，品种及时间点。这个计算结果就是主生产计划(MPS). 主生产计划在一个较长的时间段内，通常是半年，根据产品系列整合总体的生产，销售，及运作计划并最终产生针对各个产品以周为单位的总体生产计划。一个主生产计划是下一层各工厂或代工厂的生产计划及库存控制的重要依据。本文中所提及的主生产计划在一定程度上可以被称为供应链计划。

在诸多研究中，半导体行业的主生产计划很少被提及。有些著作会研究晶圆厂的产能规划问题。然而这种产能规划的时间段通常是1至2年，大大长过主生产计划。并且一般只是基于一个半导体晶圆厂针对不同产品系列展开的综合分析。在有的著作中曾提及基于整数规划来探讨集团范围内的生产策略及资源规划。一个总体模式被用来产生基于产品系列层级的计算结果。这样的模型和本文的模型有点类似在于它着重考虑了半导体制造中各前道晶圆厂及后道封装测试厂间的网络关系。也有基于一个前道晶圆厂的比较详细的模型。其中一个线形规划模型及相应的离散时件模拟被用于对不同产品投产比例的研究。基于对以往研究的探讨，可以发现主生产计划问题并不仅仅局限于半导体制造的供应链网络。在其它不同类型的行业中也有关于主生产计划方面的研究。本文主要就后道封装测试的自有工厂及外包厂的主生产计划建模并进行模拟计算。

在本文的第一段，我们会描述目前的问题。第二段，我们会建议一个整数规划模型。在最后，一些下一步的研究方向会加以阐述。

二、问题的阐述及假设

在本小节中，我们会针对所研究的问题加以描述，在第2小节中一个数学模型将会引入以优化本文的问题。我们主要致力于确定在不同的时间段不同的工厂投产的芯片数量。半导体制造包括前道及后道生产线。前道生产主要在半导体晶圆厂，而后道生产主要在封装测试厂。

本文只考虑封装测试厂。通常，生产可以外包也可以在自有工厂生产。自有工厂的模型会比外包工厂的来得复杂。我们假设需求的时间单位是周。需求包括确定的订单以及基于预测的产量。确定的订单的投产优先级要高于基于预测的产量。我们考虑上一个时间周期未达成的确定订单。基于预测的产量也被称为追加的需求。只有当产能充足的时候，我们才考虑基于预测的产量。假设我们会为了以后的订单储存一定量的成品库存。基于确定订单的销量不会超过客户订单的数量。基于预测的销量小于基于预测的产量。产能约束对于主生产计划问题很关键。在我们的模型中，我们假设每个产品的平均生产周期固定。给定的产品的完成时间。,我们能计算出它到达生产瓶颈的时间。我们在每个时间周期都会计算单位产品在生产瓶颈上消耗的时间。这个举措可以将那些工艺流程中要重复进入某一生产瓶颈的情况得到计算。由于我们无从获知代工厂的生产瓶颈，故而这种方法不适用于代工厂。因此对于代工厂，我们只是简单的计算单位时间的出货量。在这里我们规定代工厂的加工数量不能超过一个确定的界线。我们主要的工作是确定一定数量的芯片产品 p 能够在某个工厂m 内在时间周期 t 的结束前完成。我们使用周作为一个时间周期的长度，主生产计划包含6个月的时间跨度。

三、整数规划模型

在本小节中，我们基于上文中的主生产计划问题引入了一个整数规划模型

1. 决策变量，参数及目标函数

首先，我们先设定一些重要的模型纬度。以下模型纬度被加以考虑：

在这里我们用公式kmax = CTmax -1 来定义变量 kmax, 假设，我们能将所有产品的最长生产周期缩小到一个时间周期。我们可以引入以下决策变量：

目标函数是由于追加的销售预测而获得的营业额 与成本之间的差值(制造， 库存， 未完成的订单 以及选择不同生产工厂 的成本)。

2. 约束条件

以下一些条件约束被考虑到我们的主生产计划模型。

首先，我们加入库存平衡：

这个约束能够确保只有在需要的情况下一批产品才会在一个以上的工厂生产。

将非负约束及布尔约束加入模型，我们得到：

四、结论与展望