关键词: Job-Shop, 调度, 关键路径, 批量分解, 优化算法

Abstract: To shorten makespan of Job-Shop production in addition to the optimization scheduling methods, lot splitting may also be utilized opportunely for further optimizing the production plan. A simplified lot splitting Job-Shop scheduling optimization solution is presented and the principle, location, impact on the project, the steps and methods are expounded. According to the restraint of the process route, state variables are used to describe the scheduling process, based on which, a heuristic algorithm is adopted for optimal scheduling. The longest critical path in the optimal scheduling is found out with a kind of algorithm. Three rules should be followed in lot splitting: ① After optimizing scheduling first, splitting lot. ② Splitting lot should be chosen at such an equipment that the next equipment on its process route should have free time after finishing the task at the equipment. ③ The equipment - task and at least one of its follow-up processes are on the critical path. Comparing job-process waiting time and track back waiting time, the possible saving makespan between present process and the follow-up processes, the location and size of lot splitting are determined. The lot splitting and optimization reach the goal that the makespan is minimized.

Key words: Critical path, Job-Shop, Lot splitting, Optimal algorithms, Scheduling