`

据说Java程序员等电梯的时候,都想过调度算法

    博客分类:
  • java
 
阅读更多

1.传统电梯调度算法

 

1.1先来先服务算法(FCFS)

先来先服务(FCFS-First Come First Serve)算法,是一种随即服务算法,它不仅仅没有对寻找楼层进行优化,也没有实时性的特征,它是一种最简单的电梯调度算法。

 

它根据乘客请求乘坐电梯的先后次序进行调度。此算法的优点是公平、简单,且每个乘客的请求都能依次地得到处理,不会出现某一乘客的请求长期得不到满足的情况[12]。

 

这种方法在载荷较轻松的环境下,性能尚可接受,但是在载荷较大的情况下,这种算法的性能就会严重下降,甚至恶化。

 

人们之所以研究这种在载荷较大的情况下几乎不可用的算法,有两个原因:

  1. 任何调度算法在请求队列长度为1时,请求速率极低或相邻请求的间隔为无穷大时使用先来先服务算法既对调度效率不会产生影响,而且实现这种算法极其简单。

  2. 先来先服务算法可以作为衡量其他算法的标准。

 

1.2最短寻找楼层时间优先算法(SSTF)

最短寻找楼层时间优先(SSTF-Shortest Seek Time First) [14]算法,它注重电梯寻找楼层的优化。

 

最短寻找楼层时间优先算法选择下一个服务对象的原则是最短寻找楼层的时间。这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。

 

在重载荷的情况下,最短寻找楼层时间优先算法的平均响应时间较短,但响应时间的方差较大,原因是队列中的某些请求可能长时间得不到响应,出现所谓的“饿死”现象。

 

1.3扫描算法(SCAN)

扫描算法(SCAN)是一种按照楼层顺序依次服务请求,它让电梯在最底层和最顶层之间连续往返运行,在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。

 

它进行寻找楼层的优化,效率比较高,但它是一个非实时算法。扫描算法较好地解决了电梯移动的问题,在这个算法中,每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的,所有的与电梯运行方向相同的乘客的请求在一次电向上运行或向下运行的过程中完成,免去了电梯频繁的来回移动。

 

扫描算法的平均响应时间比最短寻找楼层时间优先算法长,但是响应时间方差比最短寻找楼层时间优先算法小,从统计学角度来讲,扫描算法要比最短寻找楼层时间优先算法稳定。

 

1.4 LOOK 算法

LOOK算法[18]是扫描算法的一种改进。对LOOK算法而言,电梯同样在最底层和最顶层之间运行。

 

但当LOOK算法发现电梯所移动的方向上不再有请求时立即改变运行方向,而扫描算法则需要移动到最底层或者最顶层时才改变运行方向。

 

1.5 SAFT 算法

SATF(Shortest Access Time First)[15,19]算法与SSTF算法的思想类似,唯一的区别就是SATF算法将SSTF算法中的寻找楼层时间改成了访问时间。

 

这是因为电梯技术发展到今天,寻找楼层的时间已经有了很大的改进,但是电梯的运行当中等待乘客上梯时间却不是人为可以控制。

 

SATF算法考虑到了电梯运行过程中乘客上梯时间的影响。

 

2 实时电梯调度算法

 

2.1最早截止期优先调度算法

最早截止期优先(EDF-Earliest Deadline First)调度算法是最简单的实时电梯调度算法,它的缺点就是造成电梯任意地寻找楼层,导致极低的电梯吞吐率。

 

它与FCFS调度算法类似,EDF算法是电梯实时调度算法中最简单的调度算法。

 

它响应请求队列中时限最早的请求,是其它实时电梯调度算法性能衡量的基准和特例。

 

2.2 SCAN-EDF 算法

SCAN-EDF算法是SCAN算法和EDF算法相结合的产物。

 

SCAN-EDF 算法先按照EDF算法选择请求列队中哪一个是下一个服务对象,而对于具有相同时限的请求,则按照SCAN算法服务每一个请求。

 

它的效率取决于有相同deadline 的数目,因而效率是有限的。

 

2.3 PI 算法

PI(Priority Inversion)算法将请求队列中的请求分成两个优先级,它首先保证高优先级队列中的请求得到及时响应,再搞优先级队列为空的情况下在相应的优先级队列中的请求。

 

2.4 FD-SCAN 算法

FD-SCAN(Feasible Deadline SCAN)[17]算法首先从请求队列中找出时限最早、从当前位置开始移动又可以满足其时限要求的请求,作为下一次SCAN的方向。

 

并在电梯所在楼层向该请求信号运行的过程中响应处在与电梯运行方向相同且电梯可以经过的请求信号。

 

这种算法忽略了用SCAN算法相应其它请求的开销,因此并不能确保服务对象时限最终得到满足。

 

3 电梯调度的高水平研究

以上两个小结介绍了几种在目前本人的能力上能进行研究的、简单的电梯调度算法。但是并不是说目前电梯调度只发展到这个层次。

 

目前电梯的控制技术已经进入了电梯群控的时代。

 

随着微机在电梯系统中的应用和人工智能技术的发展,智能群控技术得以迅速发展起来。

 

由此,电梯的群控方面陆续发展出了一批新方法,包括:基于专家系统的电梯群控方法、基于模糊逻辑的电梯群控方法、基于遗产算法的电梯群控方法、基于胜景网络的电梯群控方法和基于模糊神经网络的电梯群控方法。

 

4 电梯问题的需求分析

 

4.1 电梯的初始状态

本人设置的电梯的初始状态,是对住宅楼的电梯的设置。

 

  1. 建筑共有21层,其中含有地下一层(地下一层为停车场及货物运送场所)。

  2. 建筑内部设有两部电梯,编号分别为A梯、B梯。

  3. 电梯内部有23个按钮,其中包括开门按钮、关门按钮和楼层按钮,编号为-1,1,2,3,4……20。

  4. 电梯外部含有两个按钮,即向上运行按钮和向下运行按钮。建筑顶层与地下一层例外,建筑顶层只设置有向下运行按钮,地下一层只设置有向上运行按钮。

  5. 电梯开关门完成时间设定为1秒。电梯到达每层后上下人的时间设定为8秒。电梯从静止开始运行到下一层的时间设置为2秒,而运行中通过一层的时间为1秒。

  6. 在凌晨2:00——4:30之间,如若没有请求信号,A梯自动停在14层,B梯自动停在6层。

  7. 当电梯下到-1层后,如果没有请求信号,电梯自动回到1层。

     

     

 

4.2 电梯按钮功能

电梯内部的楼层按钮:电梯内部对应每一个楼层的按钮成为楼层按钮,即本章第一节提到的编号为-1,1,2,3,4……20的按钮。

 

当乘客进入电梯后按下楼层按钮,此按钮显示灰色,代表不可以用。这样就表示乘客将要去往此层,电梯将开往相应层。当电梯到达该层后,按钮恢复可以使用状态。

 

电梯内部开门按钮:当电梯达到乘客想要去往的某楼层后,乘客需要准备离开电梯,当电梯停稳后,乘客可以按下开门按钮,电梯门将打开,让用户离开。

 

如若电梯到了乘客曾经按下的楼层,但是无乘客按开门按钮,电梯将自动在停稳后1秒后自动开门。

 

电梯内部关门按钮:当所有想要乘坐电梯的乘客都进入电梯以后,准备让电梯开始运行的时候,乘客需要按下关门按钮,让电梯门关闭,使电梯进入运行状态。设置电梯的自动关门时间为8秒。

 

电梯外部向上按钮:此按钮表示上楼请求,当按下此按钮时,如果电梯到达按下此按钮的楼层,且电梯运行方向是向上的,那么电梯响将停下,并在电梯停稳之后自动开门,此请求被响应后,取消此请求信号。

 

电梯外部向下按钮:此按钮表示下楼请求,当按下此按钮时,如果电梯到达按下此按钮的楼层,且电梯运行方向是向下的,那么电梯响将停下,并在电梯停稳之后自动开门,此请求被响应后,取消此请求信号。

 

 

分享到:
评论

相关推荐

    Java程序员面试资料及简历模版

    Java程序员面试资料及简历模版 Java程序员面试资料及简历模版 Java程序员面试资料及简历模版 Java程序员面试资料及简历模版 Java程序员面试资料及简历模版 Java程序员面试资料及简历模版 Java程序员面试资料及简历...

    Java程序员面试宝典

    《Java程序员面试宝典》附带1张DVD光盘,内容为《Java程序员面试宝典》所有面试题的多媒体教学视频(共14.5小时)及免费赠送的55小时Java教学视频和5.5小时算法教学视频。授人以鱼,不如授人以渔。《Java程序员面试...

    Java程序员面试笔试宝典-何昊pdf版

    2. **算法与数据结构**:很多公司在招聘Java工程师时会考察候选人对于基础算法和数据结构的掌握程度,如排序算法、链表、二叉树等。 3. **项目经验分享**:通过实际案例分析,让读者了解如何将所学知识应用到实际...

    java程序员面试简历 WORD 模版

    2. **专业技能**:作为Java程序员,你需要列出掌握的核心技术,如Java SE、Java EE、Spring框架、MyBatis、Hibernate等。同时,提及你对多线程、并发编程、数据库设计和优化、算法和数据结构的了解。 3. **项目经验...

    java程序员算法锻炼

    猴子偷桃,分解质因数,简单加密 等经典算法!

    java程序员面试交流项目经验

    java程序员面试交流项目经验java程序员面试交流项目经验java程序员面试交流项目经验java程序员面试交流项目经验java程序员面试交流项目经验java程序员面试交流项目经验java程序员面试交流项目经验java程序员面试交流...

    java程序员转正ppt

    【Java程序员转正知识点】 1. **自我介绍**: 在转正答辩中,自我介绍是展示个人背景和技能的关键环节。作为一名Java程序员,应当包括自己的教育背景、编程经验、项目经历以及对Java语言的理解。 2. **技术成长**...

    JAVA程序员简历模板(最新版)

    【JAVA程序员简历模板】 在创建一份专业的JAVA程序员简历时,首先要明确的是,这份文档将是你在求职市场上的“名片”,它应该清晰、准确地展示你的技术能力、项目经验和教育背景。以下是一个详细的模板,帮助你构建...

    java程序员发展前景

    在技术路线上,java 程序员可以从初级程序员逐步晋升为高级 java 程序员、系统分析师、架构设计师等高端职位。在这个过程中,需要不断地学习和掌握新的技术,保持自己的技术优势和竞争力。 在管理路线上,java ...

    java程序员的成长历程

    例如,响应式编程(Reactive Programming)、微服务架构、函数式编程、Kotlin等新兴技术和语言,以及云计算、大数据、人工智能等领域的发展,都值得Java程序员去探索和掌握。 总的来说,一个Java程序员的成长历程是...

    java程序员上班那点事儿

    Java程序员需要具备一定的性能调优能力,包括但不限于JVM调优、算法优化等方面。 #### 安全性保障 随着网络安全威胁日益增多,确保应用的安全性变得越来越重要。Java程序员应关注常见的安全漏洞类型(如SQL注入、...

    java程序员等级图

    Java程序员等级图是指导开发者职业发展的重要参考,它通常涵盖了从初学者到高级专家的不同阶段,每个阶段都对应着特定的技能集和技术要求。在Java编程领域,程序员的成长路径可以分为多个等级,如初级程序员、中级...

    Java程序员上班那点事

    Java程序员上班那点事 Java程序员上班那点事 Java程序员上班那点事 Java程序员上班那点事

    java程序员简历模板(一共19套模板)

    java程序员个人简历.doc JAVA软件工程师简历范文.docx Java软件开发工程师个人简历模板.doc 个人简历(示范案例).doc 应届生Java开发个人简历.doc 非常经典java求职简历(三套-含项目介绍).doc 高级Java工程师架构师-...

    JAVA程序员培训定制课程

    Java程序员培训定制课程是专为想要深入理解和提升Java编程技能的学员设计的全面教程。这个课程涵盖了一系列核心的Java技术和实践,旨在帮助学员从初学者到精通,掌握企业级开发所需的各项技能。作为内部资料,它可能...

    java程序员总结报告

    【Java程序员年终总结】 作为一名Java程序员,我在2010年的经历让我深刻理解到学习的重要性。从初入职场的新鲜人,到能在公司独立完成项目的开发者,这段历程充满了挑战和成长。2010年,我有幸加入北京联合兴辰公司...

    java程序员规划java程序员职业规划.docx

    Java 程序员职业规划 Java 程序员职业规划是指 Java 程序员如何规划自己的职业生涯,使自己在职业道路上更快速、更自信地发展。本文将从 Java 程序员职业规划的几个方面进行详细的介绍。 一、 认识自我 在职业...

    《Java程序员》

    《Java程序员》 本书对于即将从事Java职业或初步从业的程序员来说是一本难得的好书。从生存、制胜、发展三个方面入手,为大家展示出程序员求职与工作的一幅3D全景图像。本书中既有在公司中的生存技巧,又有高手达人...

    Java程序员年中、年终述职报告PPT模板

    Java程序员在年中或年终述职报告中,通常需要展示过去一段时间内的工作成果、技术提升、项目经验以及未来规划。这份“Java程序员年中、年终述职报告PPT模板”旨在帮助他们高效地准备这类报告,通过专业且有条理的...

Global site tag (gtag.js) - Google Analytics