Scatter search algorithm for the multiprocessor task job-shop scheduling problem

作者：Fan, Kun^*; Wang, Meng; Zhai, Yafei; Li, Xinning

来源：Computers & Industrial Engineering, 2019, 127: 677-686.

DOI：10.1016/j.cie.2018.11.006

• Multi-processor tasks
• Job-shop scheduling
• Scatter search
• Improvement method

In this paper, we address the Multi-processor Task Job-shop Scheduling Problem (MTJSP) which extends the classical Job-shop Scheduling Problem (JSP): Each Job consists of a number of operations and each operation requires a set of machines to work simultaneously instead of a single one. Under the resource constraints, our goal is to minimize the makespan. Practically, MTJSP is usually found in the field of structure product manufacturing, grid computing as well as other fields with multi-step and multi-processor requirement. The problem optimization model is constructed using disjunctive formulation and solutions are represented as specific permutations for feasibility. Due to the NP-hardness of the problem, a Scatter Search (SS) based on the solution representation is developed which includes a new update scheme for the reference set to maintain diversification and an improvement method with a local search and a simulated annealing search to get better solutions. To evaluate the performance, we apply the SS procedure to both JSP benchmark instances and MTJSP instances, and the results are reported. The numerical results show that the SS has a very good performance on MTJSP instances as well as JSP instances.

• 出版日期2019-1
• 单位北京林业大学