关键词: 染缸优化调度, 并行批处理机, 不相容作业组

Abstract: Based on actual requirements of the dyeing and finishing workshop in the cloth-making factory， the scheduling model for dyeing machine was constructed. Being different from traditional scheduling models， the proposed model considered not only the merge of small jobs but also the decomposition of large jobs. Aims of the proposed model were to minimize the total tardiness and maximize the average utilization of dyeing machines simultaneously. An existing heuristic algorithm was improved and a new heuristic algorithm was proposed to solve the dyeing scheduling problem. All the proposed algorithms were applied in real-life data from the dyeing and finishing workshop in a typical cloth-making factory in Beijing. TResults showed that the proposed algorithm could not only minimize the total tardiness but also enhance the utilization of dyeing machines.

Key words: dyeing machine scheduling problem, parallel batch processing machine, incompatible job families, heuristic algorithm