Abstract: An extended job-shop model is proposed, as well as the work center and key nodes. In this new model, assembly line and batch scheduling are introduced. Based on this, this paper proposes a heuristic batch flow line scheduling algorithm in an extended job shop model, calculating the start time of remaining products by backtracking when selecting key nodes and using the greedy algorithm to sort the highest priority products. The priority rule is composed of three proxies variable including product value, time urgency and work remaining. The minimum processing batch size is set when processing. That makes parallel processing of multiple sets of equipment possible in one processing and the flow line between two adjacent processing, so as to reduce processing time and improve productivity. The simulation shows that this strategy can achieve better results.

Key words: job shop, batch, flow line, priority, heuristic algorithm

摘要： 提出了改进的job shop模型，定义了工作中心以及关键节点的概念。将流水线与批量调度策略引入到新的模型中，并在此基础上提出了一个关于扩展job shop模型的启发式批量流水线调度算法。在关键节点进行选择时，通过回溯计算其余产品的开始时间，使用贪心算法选择优先级最高的产品进行排序。该优先级法则由三个优先级变量组合而成，分别囊括了价值高低、时间紧要程度以及剩余加工时间这三个影响因素。进行加工时，设定最小加工批量，在一个工序内实现多套设备的并行加工，同时在两个相邻工序之间实现流水线加工，从而缩短加工时间，提高了生产效率。通过仿真表明该策略能取得较好的结果。

关键词: job shop模型, 批量, 流水线, 优先级, 贪心算法