Generalized Job Shop Models with Multiple Objectives

本文研究了作业车间环境下的作业调度问题。本研究的特别之处在于：(1)考虑了待调度作业的灵活路由；(2)考虑了多目标。还将开发进度质量参数分析程序。算法开发的结果将被纳入哥伦比亚大学过去四年开发的原型调度软件中。本研究中使用的术语“路由灵活性”有两层含义。在第一种情况下，路由灵活性指的是车间中的每个工作站都由多台机器填充的调度方案。访问工作站的工作只能由该站的一台机器处理。在第二种情况中，每个作业的特征是要执行的操作或处理步骤的有序序列。每个操作或工艺步骤都可以由车间中所有机器的一个子集来执行。可以执行作业所需的各种工艺步骤的机器子集可能重叠。在考虑的所有调度方案中，作业可能会循环。根据所追求的调度目标，存在几种求解调度问题的建模和求解方法。大多数现有算法关注的是传统的生产场景，其中每个作业都遵循固定的规定路线。虽然这些早期的算法可以满足许多生产情况的需要，但当作业存在灵活的路由时，它们无法有效地发挥作用。本研究工作将服务于以柔性制造系统（FMS）为代表的现代柔性车间的需求。本文的研究成果将对调度理论的发展和生产车间调度算法的应用领域的扩展做出重要贡献。

9522938 Pinedo This research addresses the problem of job scheduling in a job shop environment. Some special features of this research are (1) the consideration of flexible routing for the jobs to be scheduled, and (2) the consideration of multiple objectives. The development of procedures for parametric analysis of schedule quality will also be undertaken. The outcome of the algorithmic developments will be incorporated into prototype scheduling software that has been developed at Columbia University over the past four years. The term "routing flexibility" as used in this research is given two meanings. In the first case, routing flexibility refers to scheduling scenarios in which each workstation in the shop is populated with multiple machines. A job visiting a workstation can only be processed by one machine at the station. In the second case scenario, each job is characterized by an ordered sequence of operations or processing steps to be performed. Each operation or process step can be performed by a subset of all the machines in the shop. Subsets of machines that can perform the various process steps required by a job may overlap. In all the scheduling scenarios considered, the jobs may recirculate. Depending on the scheduling objective pursued, several modeling and solution approaches exist for solving scheduling problems. Most existing algorithms are focused on traditional production scenarios in which each job follows a fixed, prescribed route. Although, these earlier algorithms can serve the needs of many production situations, they fail to function effectively when flexible routing exists for jobs. The work done in this research will serve the needs of the modern day flexible shops as typified by flexible manufacturing systems (FMS). The outcome of the research will be a major contribution to scheduling theory and the expansion of the domain of applicability of scheduling algorithms in production shops.