EXCEL版APS自动排程

yiyiyicz

    (5) 基于排序的方法
该方法是先有可行性加工顺序，然后才确定每个操作的开工时间，并对这个顺序进行优化，它虽然属于近似算法，但有可能达到最优的排程方案。它主要包括邻近搜索法，它在生产排程领域得到了相当广泛的应用，在探索解空间时，仅对选定的成本函数值的变化做出响应，因而通用性强。这类方法包括局部探索（Local Search）、模拟退火法（Simulated Annealing）、列表寻优法（Table Search），遗传算法（Genetic Algorithms）。邻近搜索虽然可能得到最优的排程方案，但也存在各自的不足, 很多学者采取混合算法来弥补单一方法的不足。
  （6）启发式图搜索法  
    对于表述为整数规划的排程问题，最初采用分枝定界法来解决，而后其他的启发式图搜索法也被应用于解决排程问题。在文[19]中 Balas将排程排序问题用一个 disjunctive图来表示，首先构造一个可行解，采用基于隐枚举的搜索方法不断提高解的次优性；在文[40]中采用束搜索法(beam search)来识别瓶颈机器，进行排程；为了解决搜索空间太大的问题，在文[45]中通过对分枝定界法和束搜索法进行系统的分析，提出了一种过滤束搜索法(filter beam search)，用来解决单台机器提前／延期问题和加权延期的 Flow Shop问题；文[45][47]中研究了基于A*的优先树搜索法的优化作业排序问题：文[46]中针对基于树搜索的优先A*算法需要大量内存的问题，提出了一个图搜索法，并对两种方法作了比较；文[46]中为解决Job Shop排程问题对A*算法作了两点改进：1) 在搜索过程中只展开有限节点；2) 采用加权的评价函数。对于图搜索算法，如何提高搜索效率并减少内存使用以解决规模较大的问题，还需要进一步探索。
   （7）模拟退火法  
　  模拟退火算法(SA)将组合优化问题与统计力学中的热平衡问题类比，另辟了求解组合优化问题的新途径。它通过模拟退火过程，可找到全局(或近似)最优解。其基本思想为：把每种组合状态 Si看成某一物质系统的微观状态，而将其对应的目标函数C(Si)看成该物质系统在状态Si下的内能；用控制参数T类比温度，让T从一个足够高的值慢慢下降，对每个T，用 Metropolis抽样法在计算机上模拟该体系在此T下的热平衡态，即对当前状态Si作随机扰动以产生一个新状态s’，如果 C(s’)<C(S)，则接受S’为下一状态，否则以概率E-(C(S’)-C(S))接受。经过一定次数(称为&NBSPMARKOV链长)的搜索，认为系统在此温度下达到平衡，则降低温度T再进行搜索，直到满足结束条件。
    模拟退火法的几个重要部分为：生成函数(generation)、容忍函数(acceptance function)、 Markov链长、降温过程和结束准则。模拟退火法的改进算法有加温退火法、有记忆的模拟退火法等。文[47]中为Flow Shop问题求解构造了一类模拟退火法，并通过六种不同的随机抽样方式分析了算法渐近收敛于全局最优解，分别解决了具有最小Makespan指标且具有无限中间存储(UIS)、有限中间存储(FIS)和无中间存储(NIS)的 Flow Shop排序问题；文[43]提出了一种改进的模拟退火法，用来解决具有最小 Makespan指标的 Flow Shop排序问题，并与禁忌搜索法等进行了比较；文[48]用模拟退火法进行机器分组；文[49]用模拟退火法求解有资源约束的排程问题。另外，模拟退火法也可与其他方法相结合进行求解，如文[42]中先用贪心法(greedy法)搜索，将得到的作业序列作为初始解，再用模拟退火法求解单机排程问题，其结果表明这种方法比单纯用模拟退火法和贪心法要好；文[44]中提出了将模拟退火法与启发式算法相结合的方法，求解具有交货期约束的Job Shop排程问题。由于模拟退火法能以一定的概率接受差的能量值，因而有可能跳出局部极小，但它的收敛速度较慢，很难用于实时动态排程环境。

yiyiyicz

    （8）禁忌搜索法  
　   对于复杂的组合优化问题，禁忌搜索也是一种通过领域搜索以获取最优解的方法，Glover曾在文[44][45]中叙述了它的基本原理。禁忌搜索是一种迭代方法，它开始于一个初始可行解 S，然后移动到领域 N(S)中最好的解s’，即s’对于目标函数F(S)在领域 N(S)中是最优的。然后，从新的开始点重复此法。为了避免死循环，禁忌搜索把最近进行的T个移动（T可固定也可变化）放在一个称作 tabu list的表中(也称短期记忆)，在目前的迭代中这些移动是被禁止的，在一定数目的迭代之后它们又被释放出来。这样的tabu list是一个循环表，它被循环地修改，其长度T称作Tabu size。最后，还须定义一个停止准则来终止整个算法。由于tabu list的限制，使其在搜索中有可能跳出局部极小。文[33][34]分别提出了解决flow shop排程问题的禁忌搜索算法。在文[37]中为了更有效地搜索解空间，引入了插入和移动相结合的机制提高了搜索效率。文[48]中采用了并行禁忌搜索法以加快搜索速度。文[49]中针对求解公共交货期下带有等待时间惩罚的提前／拖期单机排程问题，提出了一种禁忌搜索法。
    （9）神经网络优化  
　   Hopfield神经网络模型的提出为求解各种有约束优化问题开辟了一条新途径，用 Hopfield网络解决TSP问题就是其在组合优化问题中的最成功的应用之一。它的主要思路是：通过一个Lyaplmov能量函数构造网络的极值，当网络迭代收敛时，能量函数达到极小，使与能量函数对应的目标函数得到优化。文[44]介绍了一种随机 Hopfield网络来解决 Job Shop排程问题的方法；文[46]中为了解决大规模问题，又提出一种改进的Hopfield网络的整数线性规划神经网络方法来解决 Job Shop排程问题；文[51]中也提出了一种用于解决Job Shop排程问题的神经网络方法。
    （10）遗传算法  
　   美国Michigan大学的J.H.Holland于本世纪末提出了一种新的并行优化搜索方法：遗传算法(Genetic Algorithm)，它是一种基于进化论优胜劣汰、自然选择、适者生存和物种遗传思想的随机优化搜索算法，通过群体的进化来进行全局性优化搜索。它以其很强的并行性和很高的计算效率正日益受到人们的关注。它对组合优化问题求解的主要过程是：给定一组初始解作为一个群体，通过选择、交换和变异等遗传操作符来搜索问题的最优解。文[37]中提出了一种基于遗传算法的启发式方法，用于解决以最小化Makespan为指标的flow shop排程问题；文[39]用遗传算法解决Job shop排程问题；有的学者将遗传算法与图搜索法相结合，利用遗传算法进行知识的推理、启发，再用过滤束搜索法(filter beam search)进行优化搜索，以得到高质量的 FMS静态排程；文[27]提出了一种并行遗传算法，试图解决常规遗传算法在解决FMS排程问题时产生的计算速度较慢及过早收敛等问题。
    总的来说，遗传算法的最大优点是通过群体间的相互作用，保持已经搜索到的信息，这是基于单次搜索过程的优化方法所无法比拟的。但是，遗传算法也存在着计算速度较慢的问题。
    (11) 基于智能的排程方法
     近年来受实际需要的推动，基于知识的智能排程系统和方法的研究取得了很大的进展。人工智能在60年代就将计划问题作为其应用领域之一，但直到80年代，以Carnegie—Mellon大学的M.Fox为代表的学者们开展基于约束传播的ISIS(Intelligent Scheduling and Information System)的研究为标志，人工智能才真正开始应用于排程问题。基于知识的排程方法是用专家系统自动产生排程或辅助人去排程。它是将传统的排程方法与基于知识的排程评价相结合的方法。在八十年代后期，几位学者先后开展了基于排程系统处于不同的状态，采用不同的排程规则策略的动态排程方法的研究。它们研究的共同特点是：在支持某些活动发生的资源条件具备时(称为决策点)，根据系统当时所处的属性状态，决定采取何种规则(策略)，确定或选择活动发生的顺序和时间，即状态指导的智能排程方法。

yiyiyicz

排程方法存在的问题：
    排程领域中的大部分问题都具有NP问题，虽然对它的研究已有几十年的历史，但至今尚未形成一套系统的方法和理论，理论研究与实际应用之间还存在着很大差距。尤其随着JIT（Just-In-Time）思想的广泛采用，E/T（Earliness/Tardiness）排程问题，即使得工件尽量按交货期完成，变得越来越突出。实际应用中的排程方法能够响应系统的动态变化，但不能保证得到好的排程：一些理论上的最优化方法能提供最优排程，但由于其计算的复杂性，并且忽略了很多实际因素，离实际运用还有较大距离。基于最优化的方法，诸如动态规划算法与分枝定界算法等等，由于其大多数是建立在对可能排程的部分枚举上，因此只能解决小规模的排程问题，距离实用还有较大距离。
    由于大多排程问题属于一类NP困难组合问题，因此寻找具有多项式复杂性的最优算法几乎是不可能的。但因其解的最优性、至今仍激发着学者们进行不断的探索。各种近似／启发式方法、诸如基于规则的算法等，由于能在合理的时间内产生比较满意的排程，因此广泛应用于实际排程中，但其往往对所得的排程解的次优性不能进行评估。在这方面有必要探索更好的近似最优排程算法，可以考虑增加合理的计算时间代价，提高解的次优性。各种基于统计优化的方法、诸如模拟退火法、遗传算法等，提供了一种解决排程优化问题的新途径，但同别的优化算法类似，其也存在着一定程度的校举、一般来说收敛到最优解很慢，并且对于判断解的最优性也很困难。在这方面也需要做进一步的研究。
    在实际车间生产排程中，车间生产计划与车间生产排程往往是分层进行的，但这可能造成计划在实际排程中的不可行问题，如何将计划与排程结合考虑，以求总体的优化也是需要进一步研究的。另外，还有很多有待进一步研究的问题，比如实际车间排程的多目标性等。排程理论、方法与应用的研究是一项非常艰巨的工作，目前人们还在进行各种各样的探索性研究工作。

yiyiyicz

APS排程关键技术 ：

    寻找车间排程的最优解，并没有一个确定的算法。许多约束条件，使得实际的排程问题变得非常困难，比如：设备的可选性、制造环境的动态与不确定性、约束条件的矛盾（最小加工时间与最大设备利用率）等等，实际上，生产排程问题大部分是集中于简化问题，然后寻找最优解或次优解。研究与开发排程系统面临的关键问题主要有：
    信息表达：包括排程任务及特殊信息（工作能力、可选生产计划等）的描述。
    交互性设计：交互性不单指人机界面的问题，它应支持人对排程过程的直接参与，因为纯粹的自动化排程是不现实的，它忽略了具有最终决策职责的排程行家的重要作用。
    多种排程方法的结合。
    与已有信息环境的集成：现有企业都已具有了自己的信息技术基础结构，排程系统应能与现有环境进行通讯与信息交换，并作为信息系统的一部分，因此应提供与标准系统（如数据库、网络等）的通用接口。
典型应用  
    由于排程问题的复杂性，实际生产排程的目标应定为寻找一个好的、可行的的解决方案而常常不是最优的方案。尽管有大量的解决排程的方案，但是只有少数的方法应用于实际。其中，基于智能的排程方法应用人类专家的经验及特殊领域的知识，在解决排程问题上已经做出了很多成绩。
    德国Oldenburg大学的Jurgen Sauer教授及高级软件工程师Ralf Bruns联合研究基于知识的排程系统，为实际的排程系统建立了一个通用的框架，它支持算法的重用并把基于知识的技术应用于环境的组织，同时适应各种动态的变化。他们把这一思想成功地应用于实际，并建立了各种实用的排程系统，其中有连续过程的排程系统、医疗行业排程系统及最有普遍意义的——Job-Shop排程系统。在解决Job-Shop计划排程问题中，这些由大学研究人员及实际应用人员组成的项目组，首先实现了原型系统，并不断对其进行修改扩充，直到它能满足实际的要求，然后把该系统应用于生产管线零配件的Siekmann Fittings 公司，设计开发了PSY（生产计划与排程系统）。该系统使用Prolog语言在SunSparc工作站上开发，包括：人机界面、人机编程接口、与关系数据库（oracle等）的接口，排程系统能够做长期和短期排程计划，能显示排程表与排程过程，用户可以直接参与选择排程策略及修改命令与操作。该系统的使用，极大地减少了排程时间，满足用户的需求，功能强大，目前已开始商品化并走向市场。

yiyiyicz

文献
[1] Blackstone, J. H., Phillips, D. T. And Hogg, G. L. (1982) A state-of-the art survey of dispatching rues for manufacturing job shop operation．International Journal of Production Research 20, 27-45.

[2] Kiran, A. S. And Smith, M. S. (1984) Simulation studies in job shop scheduling: a survey. Computers and Industrial Engineering, 8, 46-51.

[3] Montazeri, M. And Van Wassenhove, L. N.(1990) Analysis of scheduling rules for an FMS. International Journal of Production Research 28, 785-802.

[4] KHALID KOUISS, etc, Using multi-agent architecture in FMS for dynamic scheduling. Journal of Intelligent Manufacturing, 1997, 8, 45~47

[5] A.Kwork and D.NORRIE, A multi-agent environment in robotics. Journal of Robotic, 1991 V.9 431~440.

[6] Elpida S T. Agentifying the Process：Task - Based or Robot - Based Decomposition．IEEE Conference on System, Manufacturing and Synbenetics, 1994：582~587

[7] Balasubramania S,Douglas H N,Morikawa K et al. Evolution of CIM with Genetic Algorithm. IEEE 1994:746~749.

[8] Garey, M.R., R.L. Graham and D.S. Johnson, “Performance Guarantees for Scheduling Algorithms”, Operations Research, 1978, Vol.26, pp3-21

[9] E.L.Lawler, “Optimal sequencing of a single machine subject to precedence constraints”, Management Sci. 1973, Vol.19, pp544-546

[10] C.L.Monma, “Sequencing to minimize the Maximum job cost”, Oper. Res. 1980, Vol.28, pp942-951

[11] T.S. Abdul-razaq, C.N. Potts, “Dynamic programming state-space relaxation for single-machine scheduling”, Joper. Res. Soc., 1988, Vol.39, pp141-152

[12] Carlier, “Scheduling jobs with release dates and tails on identical machines to minimize makespan”, European J.Oper. Res., 1987, Vol.29, pp2980-306

[13] J.Grabowski, “A new algorithm of solving the flow-shop problem”, Operations Research in Progress, Reidel. Dordrecht, 1983, pp57-75

[14] Y.Cho, S.Sahni, “preemptive scheduling of independent jobs with release and due times on open, flow and job shops”, Oper. Res., 1981,Vol.29, pp511-522

[15] E.L.Lawler, J.K.Lenstra, A.H.G.Rinnooy Kan, D.B.Shmoys, “Sequencing and Scheduling: Algorithms and Complexity”, Operations Research and Management Science, Vol.4, Edited by S.C. Graves.

[16] Garey, M.R., Johnson, D.S. and Sethi, R. “The complexity of flowshop and jobshop scheduling.”, Mathematics of Operations Research, 1976, p117-129

[17] S.C.Sarin, S.Ahn, A.B.Bishop, “An improved branching scheme for the branch and bound procedure of scheduling n jobs on m machines to minimize total weighted flowtime”, Internat.J.Production res., 1988, Vol.26, pp1183-1191

[18] C.N.Potts, L.N.van wassenhove, “A branch and bound algorithm for the total weighted tardiness problem”, Oper.Res., 1985, Vol.33, pp363-377

[19] Balas, E. “Machine-Sequencing via Disjunctive Graphs: An Implicit Enumeration Algorithm”, Oper.Res., 1969, Vol.17, pp941-957

[20] Xchrage, L., “Solving Resource-Constrained Net work Problems by Implicit Enumeration-Nonpreemptive Case”, Oper.Res., 1970, Vol.18, pp263-278

[21] Fisher, M.L., “Optimal Solution of Scheduling Problems Using Lagrange Multipliers”, Oper. Res., 1973, Vol.21, pp1114-1127

[22] J.K.Lenstra, written communication to E.Balas, May 1, 1986

[23] Montazeri, M. and L.N.Van Wassehove, “Analysis of scheduling rules of an FMS”, Int. J.Prod. Res., 1990, Vol.28, No.4, pp785-802

[24] Doublgeri, Z., G.D’alessandro and N.Magaletti, “A hierarchical knowledge-based scheduling and control for FMSs”, Int. J. Computer integrated Manufacturing, 1993, Vol.6, No.3, pp191-200

[25] Wu, Szu-Yung David and Richard A. Wysk, “An application of discrete-event sumulation to on-line control and scheduling in flexible manufacturing”, Int.J.Prod.Res., 1989, Vol.27, No.9, pp1603-1623

[26] Jiang, Chang-Qing, Singh, Madan G., and Hindi, Khalil S., “Optimized Routing in flexible manufacturing systems with blocking”, IEEE Trans. on Systems, Man, and Cybernetics, 1991, Vol.21, No.3, pp5889-595

[27] Lee, D.Y. and F.Dicesare, “Scheduling flexible manufacturing systems using petri nets and heuristic search”, IEEE Trans. on Robotics and Automation, 1994, Vol.10, No.2, pp123-132

[28] Ow, Peng Si and Thomas E.Morton, “Filtered beam search in scheduling”, Int. J. prod. Res., 1988, Vol.26, No.1, pp35-62

[29] 田澎，杨自厚，张嗣瀛，“同顺序（flow shop）排序问题的模拟退火求解” ，信息与控制，1994，Vol.23, No.3, pp133-139

[30] Jeffcoat, David E. and Robert L. Bulfin, “Simulated annealing for resource-constrained scheduling”, European Journal of Operational research, 1993, Vol.70, pp43-51

[31] Mittenthal, John, Madabhushi Raghavachari and Arif I. Rana, “A hybrid simulated annealing approach of single machine scheduling problems with nonregular penalty functions”, Computers Ops. Res., 1993, Vol.20, No.2, pp103-111

[32] Tzafestas, Spyros and Alekos Triantafyllakis, “A new adaptively weighted combinatorial dispatching rule for complex scheduling problems”, Computer Integrated manufacturing Systems, 1994, Vol.7, No.1, pp7-15

[33] 高红，熊光楞，“决策规则在仿真排程中的应用” ，控制与决策，1995, Vol.10, No.2, pp114-118

[34] 王家钦，“生产排程的一种启发式规则” ， 清华大学学报，1995, Vol.35, No.5,pp27-32

[35] 龙连文，王月霞，“作业排序专家系统模型中的知识处理方法” ，控制与决策，1992, Vol.7, No.3, pp236-238

[36] Leung, L.C., S.K.Maqnheshwari and W.A.miller, “concurrent part assignment and tool allocation in FMS with material handling considerations”, Int. J. Prod. Res., 1993, Vol.31, No.1, pp117-138

[37] Vassilis S.Kouikoglou, Yannis A.Phillis, “An Exact Discrete-Event Model and Control Policies for Production Lines with Buffers”, IEEE Trans. On automatic control, Vol.36, No.5, May, 1991

[38] Panayotis D.Sparaggis, Christos G.Gassandras, and Don Towsley, “On the Duality Between Routing and Scheduling Systems with Finite Buffer Space”, IEEE Trans. on automatic control, Vol.38, No.9, Sept. 1993

[39] 刘瑞华，涂奉生，“Fork-Join排队网络的建模与稳定性” ，控制与决策，Vol.9, No.3, 1994, pp131-135

[40] A.K.Sen, A.Bagchi and B.K.Sinha, “Admissible search for minimum penalty sequencing of jobs with setup times on two machines”, in Proc. IJCAI-91, Int. Joint Conf. Artificial Intellig. Sydney, Aug. 1991, pp178-183

[41] Anup K.Sen., Amitava Bagchi, and Ramkumar Ramaswamy, “Searching Graphs with A*: Applications to Job Sequencing”, IEEE Trans. on Systems, Man, and Cybernetics, 1996, Vol.26, No.1, pp168-173

[42] Hisao Ishibuchi, Shinta Misal, Hideo Tanaka, “Modified simulated annealing algorithms for the flow shop sequencing problem”, 1995, European Journal of Oper. Res., Vol.81, pp388-398

[43] Zesheng He, Taeyong Yang, Andy Tiger, “An exchange heuristic imbedded with simulated annealing for due-dates job-shop scheduling”, 1996, European Journal of Oper. Res., Vol.91, pp99-117

[44] Glover F., “Future Paths for Integer Programming and Links to Artificial Intelligence”, Computer & Oper. Res., 1986, Vol.13, No.5, pp533-549

[45] Glover F., “New Approaches for Heuristic Search: A Bilateral Linkage with Artificial Intelligence”, European Journal of Oper. Res., 1989, Vol.39, pp119-130

[46] Widmer.M., and Hertz, A., “A new heuristic method for the flow shop sequencing problem”, European Journal of Oper. Res., 1989, Vol.41, No.2, pp186-193

[47] Taillard, E., “Some efficient heuristic methods for the flow shop sequencing problem”, European Journal of Oper. Res., 1990, 47/1, pp65-74

[48] Languna, Manuel, J.Wesley Barnes and Fred Glover, “Intelligent scheduling with tabu search: An application to jobs with linear delay penalties and sequence-dependent setup costs and times”, Journal of Applied Intelligence, 1993, No.3, pp159-172

[49] Garcia, Bruno-laurent, Potvin, Jean Yves and Rousseau, Jean-Marc, “A parallel Implementation of the tabu search heuristic for vehicle routing problems with time window constraints”, Computers Ops. Res., 1994, Vol.21, No.9, pp1025-1033

[50] 尹新，杨自厚，“用tabu search方法解带有等待时间惩罚的提前/拖期排程问题” ，系统工程理论方法应用，1995, Vol.4, No.1, pp30-35

[51] Foo Y.S., Y.Takefuji, “Integer linear programming neural networks for job-shop scheduling”, IEEE Int. Conf. On NNS, 1988, San Diego

yiyiyicz

仔细看看你的程序，好像和这些算法关系不大啊？
程序中的module1中有sheets("Scehduling")，但是工作薄中没有。可能是想用在maincotrol表的AC列之后，做进度条用吧？
模块1是用了
主要的工作都集中在maincontorl表中的“AA  AB”两列，也就是27,28两列
是这样吗？

yiyiyicz

你的模块1中第一个 if end 看不懂啊
m.Cells(4, l) + m.Cells(8, l) + m.Cells(12, l) + m.Cells(16, l) + m.Cells(20, l)，是上班时间，我理解为规定的工作时间。在你的sheet4表中，他们永远是0
而m.Cells(6, l) + m.Cells(10, l) + m.Cells(14, l) + m.Cells(18, l) + m.Cells(22, l) ，是当日耗时，我理解为实际工作时间。在你的sheet5中，也永远是0
n.Cells(i, 5)，在sheet5中设定的都是1，换产时间。
那么，你的 do while loop 好像全都跳过去了
是不是还有其他的东西，没有在这工作薄中反映出来？

iddison

理论文献

181408321

好。。。。

IEZZIA

大家看起来都很厉害啊！求助，求助，不知道这里面有没有从事工业工程的前辈，我们主管叫我用vb控制excel做人机作业分析，即在vb里面写一段程序然后调用excel自动生成一张人机作业分析表，暂定是一人两机，人装卸机器的时间都是自己定，尝试了很多办法都行不通，请高手相助，不胜感激！