单机调度研究：加工时间与开工时间或位置关系

"王成飞和张玉忠的论文‘Single Machine Scheduling with Processing Time Functions of Starting Time or Position’探讨了单机排序问题，其中工件的加工时间取决于开工时间或位置的函数。" 在该论文中，作者关注的是两种类型的加工时间函数：一种是基于开工时间，另一种是基于工件的位置。这种加工时间模型引入了一种更复杂的优化挑战，因为工件的处理时间不再恒定，而是随着开始加工的时间或在生产线上的位置变化而变化。这样的设定在实际生产环境中具有较高的现实意义，例如，可能由于设备老化、温度变化或操作员疲劳等因素导致加工效率随时间或顺序改变。 针对加工时间依赖于开工时间的模型，作者在特定条件下找到了最小化最大完成时间和总完成时间的最优调度策略。最大完成时间（Makespan）是最长的单个作业完成时间，而总完成时间是所有作业完成时间的总和。这两个目标在调度优化中都是常见的考量因素，因为它们直接影响到生产效率和等待时间。 对于依赖于位置的加工时间模型，作者为每个最小化最大完成时间和总完成时间的问题提供了最优解决方案，并且提出了一种贪婪算法来解决总加权完成时间的问题。贪婪算法是一种常用的有效优化策略，它在每一步选择局部最优解，期望最终达到全局最优解。在单机排序问题中，这可能意味着根据某些规则（如作业大小、优先级等）逐步安排工件的加工顺序。 这篇论文属于首发论文，得到了国家自然科学基金和高等教育博士学科专项科研基金的支持，反映了作者王成飞和张玉忠在排序理论与应用领域的研究深度。王成飞作为在读博士，其研究方向直指实际工业问题，这表明他的工作旨在解决生产计划和调度中的复杂问题，提高生产效率。 总结来说，这篇论文为处理加工时间非线性变化的单机排序问题提供了新的理论基础和算法工具，对于工业工程、运营管理等领域有着重要的实践指导价值。通过深入理解和应用这些方法，企业可以更好地规划生产流程，减少等待时间，提升整体生产效率。