"这篇论文是《应用数学与物理学杂志》(Journal of Applied Mathematics and Physics)在2017年发布的一篇文章,由Maryam Ehsaei和Duc T. Nguyen共同撰写。文章的DOI为10.4236/jamp.2017.511177,探讨了用于解决机器调度问题的新启发式算法,旨在最小化车间作业调度问题(JSP)的完工期限(makespan)。"
文章中提出的启发式算法是为了应对车间作业调度问题,这是一个典型的优化问题,通常在制造业和生产环境中出现。在JSP中,任务(作业)需要在一系列特定顺序的机器上执行,目标是找到一个最优的作业顺序,以最小化所有作业完成的时间,即完工期限。
新算法的独特之处在于它结合了多种调度规则来确定每台机器上的作业顺序。这些规则包括:
1. **最短处理时间**(Shortest Processing Time, SPT):优先处理处理时间较短的作业,以快速释放机器资源。
2. **最早到期日期**(Earliest Due Date, EDD):考虑每个作业的截止日期,优先处理到期时间最早的作业,以避免延误。
3. **最少延迟**(Least Tardiness):衡量作业完成与预定到期日期之间的差距,减少作业过期的可能性。
4. **先到先服务**(First-Come, First-Served, FCFS):按照作业到达的顺序进行处理,这是一种基本但公平的策略。
与其他启发式算法相比,本文提出的方法还考虑了用户指定的每个作业的到期日期,这使得算法更加灵活,能更好地适应实际生产环境中的需求。
实验部分,作者对比了新算法与经典的Shifting Bottleneck算法,结果显示,当作业数量小于或等于机器数量时,新算法在减少完工期限方面表现更优。对于作业数量大于机器数的情况,当作业与机器数量比例小于2.1时,新算法依然表现出较高的效率。然而,当这个比例超过2.1时,两种方法的性能差异不再明显,无法得出一致的结论。
这项研究提供了一种新的、结合多种调度策略的启发式算法,对于某些特定条件下的机器调度问题,该算法能有效缩短完工期限,提高生产效率。然而,对于作业数量远超机器数量的复杂情况,需要进一步的研究来确定最佳解决方案。