Deakin University
Browse

File(s) stored somewhere else

Please note: Linked content is NOT stored on Deakin University and we can't guarantee its availability, quality, security or accept any liability.

Mathematical Modeling and a Novel Heuristic Method for Flexible Job-Shop Batch Scheduling Problem with Incompatible Jobs

journal contribution
posted on 2023-03-01, 05:13 authored by Bin Ji, Shujing Zhang, Samson YuSamson Yu, Binqiao Zhang
This paper investigates a novel flexible job-shop scheduling problem, where the machines have batch-processing capacity, but incompatible jobs cannot be processed in a batch (FJSPBI) simultaneously. This problem has wide applications in discrete manufacturing, especially in chemical and steel casting industries. For the first time, in this study, a 3-indexed mixed-integer linear programming (MILP) model is proposed, which can be efficiently and optimally solved by commercial solvers for small-scale problems. In addition, an improved large neighborhood search (LNS) algorithmic framework with an optimal insertion and tabu-based components (LNSIT) is proposed, which can achieve high-quality solutions for a large-scale FJSPBI in a reasonable time. A perturbation strategy and an optimal insertion strategy are then additionally embedded to improve the exploitation and exploration ability of the algorithm. The proposed model and algorithm are tested on numerous existing benchmark instances without the incompatibility characteristics, and on newly generated instances of the FJSPBI. The experimental results indicate the effectiveness of the proposed MILP model and the algorithm, including the proposed strategies, and the optimal insertion strategy can significantly reduce the computational burden of the LNS algorithm. The comparison results further verify that the proposed LNSIT can directly solve the specific flexible job-shop batch scheduling problem without incompatibility, with better results than existing methods, especially for large-scale instances. Additionally, the impacts of a wide range of characteristics, including batch capacity, incompatibility rate, instance scale, and machine processing rate, on the performance of the LNSIT and the scheduling results are analyzed and presented.

History

Journal

Sustainability

Volume

15

Article number

1954

Pagination

1-26

Location

Basel, Switzerland

eISSN

2071-1050

Language

eng

Publication classification

C1 Refereed article in a scholarly journal

Issue

3

Publisher

MDPI AG

Usage metrics

    Research Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC