Minimizing the makespan for a serial-batching scheduling problem with arbitrary machine breakdown and dynamic job arrival

作者：Pei, Jun; Liu, Xinbao^*; Fan, Wenjuan; Pardalos, Panos M.; Migdalas, Athanasios; Goldengorin, Boris; Yang, Shanlin

来源：International Journal of Advanced Manufacturing Technology, 2016, 86(9-12): 3315-3331.

DOI：10.1007/s00170-016-8408-8

• Serial-batching scheduling
• Heuristic algorithm
• Dynamic arrival
• Machine breakdown
• Setup time

Many dynamic events exist in real manufacturing systems, such as arbitrary machine breakdowns and dynamic job arrivals, which makes the scheduling problem even more complicated. In this paper, we address a serial-batching scheduling problem with the above dynamic events. Jobs need to be processed on the serial-batching machines of two manufacturers and then transported by vehicles to a customer for further processing. The objective of the scheduling problem is to minimize the makespan, and the problem is proved to be strongly NP-hard. Some structural properties and a lower bound of the problem are also proved or derived. On the basis of job arrival times, we divide the problem into two phases and propose different rules regarding these two phases. Based on these properties and rules, a heuristic algorithm is developed to solve the problem and its worst case performance is analyzed. The heuristic algorithm is tested on a large set of randomly generated problem instances, and the relative gaps between the found lower bound and the solutions of the proposed heuristic algorithm are reported. The experimental results illustrate the high efficiency and effectiveness of the proposed heuristic algorithm compared with other four classic approaches.

• 出版日期2016-10
• 单位合肥工业大学