Auction-based approach to the job-shop problem with parallel batch processing and a machine availability constraint

Abstract

In military manufacturing enterprises, exceptionally high product performance standards are generally met by using heat treatment followed by machining. These procedures are typically parallel batch-processing (BP) scheduling problems and job-shop problems, respectively. A mixed-integer nonlinear programming model is created to describe the problem with a machine availability constraint, which is divided into two stages: BP and machine processing (MP). Furthermore, an auction-based approach is developed in which jobs are categorized into batches during the BP stage and resources are allocated to operating machines during the MP stage. A local search operator is then applied to optimize the obtained feasible solutions. Benchmark instances are enlarged to adapt to the proposed problem. The approach is tested and compared to existing algorithms, and statistical analysis is performed using SPSS Statistics. The results show that the auction-based approach is effective and stable, and has absolute advantages in solving large-scale instances.

KEYWORDS:

• Job-shop scheduling
• parallel batch processing
• auction-based approach
• machine availability constraint
• local search

Acknowledgement

The authors appreciate the financial support from the National Natural Science Foundation of China.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This article is financially supported by the National Natural Science Foundation of China [grant numbers 71831003 and 71702028] and Fundamental Research Funds for the Central Universities [grant number N182804001].