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

• 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.

Subject headings

TEKNIK OCH TEKNOLOGIER  -- Maskinteknik -- Produktionsteknik, arbetsvetenskap och ergonomi (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Mechanical Engineering -- Production Engineering, Human Work Science and Ergonomics (hsv//eng)

Keyword

Industrial Logistics

Industriell logistik

Intelligent industrial processes (AERI)

Intelligenta industriella processer (FOI)

Publication and Content Type

ref (subject category)

art (subject category)