Auction-based approach with improved disjunctive graph model for job shop scheduling problem with parallel batch processing. (April 2022)

• Record Type: Journal Article
• Authors: Zeng, Chengkuan; Qi, Guiqing; Liu, Zixuan; Tang, Jiafu; Fan, Zhi-Ping; Yan, Chongjun
• Is Part Of: Engineering applications of artificial intelligence. Volume 110(2022)
• Publication Date: 2022-04
• Subjects: Job shop scheduling -- Parallel batch processing -- Auction-based approach -- Improved disjunctive graph model; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2022.104735
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: The job-shop scheduling problem (JSSP) is encountered in several industries, including the military where heat treatment is applied prior to the machining process in production. This study aims to minimize the overall make-span of a JSSP with parallel batch processing. The problem is formulated as a mixed-integer linear programming model. Feasible solutions are derived from an auction-based approach for forming batches, allocating operation machines, and scheduling. An improved disjunctive graph model is further developed to search for better solutions. We conduct numerical experiments to test a set of benchmark instances. A comparison of the results with those obtained applying other existing algorithms and CPLEX demonstrates the effectiveness and stability of the proposed auction-based approach and improved graph model. Furthermore, a statistical analysis using IBM SPSS shows that the proposed auction-based approach has an absolute advantage in solving medium-scale and large-scale instances of JSSP with batch processing.