In the context of modern manufacturing, the workshop scheduling problem remains a focal point of research, particularly within the foundry industry, which serves as a foundational pillar of the manufacturing sector. Sand casting foundries are characterized by long and complex process flows, intricate workpiece production scheduling, and significant challenges in resource allocation. Traditionally, many sand casting foundries rely heavily on the experience of their personnel to devise production schedules, which often leads to suboptimal efficiency, wastage of materials and energy, and elevated carbon emissions. With the advent of Industry 4.0 and the “Made in China 2025” initiative, information-driven and intelligent production management models have become critical for enhancing the competitiveness of enterprises. Consequently, researching intelligent production scheduling for sand casting foundries has emerged as a key pathway to improve production efficiency and reduce carbon emissions.
Our research proposes a comprehensive, whole-process low-carbon production scheduling solution specifically designed for sand casting foundries. We constructed a low-carbon scheduling model that integrates carbon emission constraints with production process constraints, aiming to balance emission reduction with production efficiency. To address the batch processing challenges inherent in processes like melting and heat treatment, we developed novel batch grouping rules based on a concept of “batch rationality” to evaluate the efficacy of different batch combinations. The model was solved using the NSGA-III algorithm, and its validity was verified through simulation examples based on a typical sand casting foundry production scenario. The results indicate that the constructed model is reasonable, and for a candidate pool of 25 workpieces, the NSGA-III algorithm demonstrates superior convergence and comprehensive performance compared to other multi-objective algorithms, proving its effectiveness in solving complex scheduling problems.
The workshop scheduling problem is widely recognized as an NP-hard problem, for which efficient solutions are still being sought. During the production process in a sand casting foundry, enterprises must contend with various constraints, including order requirements, processing characteristics, and equipment capacity. The goal is to rationally allocate resources such as machinery, materials, and energy to optimize production efficiency, reduce costs, and ensure timely delivery. The typical production flow of a sand casting foundry is illustrated, which shows the sequential and parallel nature of the processes. The scheduling problem in a sand casting foundry can be classified as a variant of the flow shop scheduling problem, specifically a hybrid flow shop scheduling problem (HFSP). Furthermore, because workpieces are processed in batches in certain stages (like melting and heat treatment) and may be processed on machines with different speeds at the same stage, the problem can be further defined as a Batch-HFSP(Qm). This model is more realistic than the standard HFSP but also more complex to solve.
Mathematical Model for Low-Carbon Scheduling
Problem Description and Assumptions
Before constructing the mathematical model, we must clarify the actual production scenario of a typical sand casting foundry. The processing methods are as follows: (1) Within a single process, processing is continuous and cannot be interrupted until all workpieces in the group are completed. (2) Throughout the whole process, processing is continuous; a workpiece can immediately start its next process once the previous one is completed, provided the machine is available. (3) For any single-piece processing stage, a machine can process only one workpiece at a time. (4) For any single-piece processing stage, a workpiece can only be processed on one machine at a time. (5) For any batch processing stage, a machine can process only one batch at a time, and all workpieces within that batch have the same processing time for that stage. (6) For any batch processing stage, a batch can only be processed on one machine at a time.
To facilitate theoretical research, we made the following assumptions based on the Batch-HFSP(Qm) model: (1) At the start of processing, all machines are idle and workpieces can be assigned to any machine. (2) Setup and cleaning times before the first and after the last process are ignored. (3) Internal transportation times between successive serial processes for the same workpiece are ignored; only actual processing time is considered. (4) Machine start-up and shutdown times are ignored; all machines are turned on at the beginning of the first process and turned off only after all workpieces are completed.
Objective Functions
The objective functions are the ultimate goals of the scheduling plan. Combining the constructed carbon emission estimation model for castings in a sand casting foundry, we propose three objective functions to measure the quality of the scheduling plan.
Objective function O1 represents the minimization of the maximum completion time, also known as the makespan. This is a fundamental indicator of the scheduling plan’s efficiency and is defined as the time when the last workpiece finishes processing.
$$ O_1 = \min \left( \max_{i \in [1,n]} (ET_i) \right) $$
where n is the total number of workpieces and ETi is the completion time of the last process of workpiece i.
Objective function O2 represents the minimization of the penalty for deviation from the delivery date. This measures how well the scheduling plan satisfies customer delivery requirements.
$$ O_2 = \min \left( \sum_{i} \alpha \left| T_i – D_i \right| \right) $$
where α is the penalty coefficient for earliness or tardiness, Ti is the total processing time of workpiece i, and Di is the number of days until the delivery date for workpiece i.
Objective function O3 represents the minimization of carbon emissions. This is a key indicator of the scheduling plan’s ability to reduce carbon emissions.
$$
O_3 = \min \left(
RM\_EF \sum_i m_i + E\_EF \sum_i \sum_j B_i B_{ijk} P_k T_{ij} + E\_EF \sum_h \sum_i A_i A_{ih}^m E_{hk}^m P_k T_m m_i + F\_EF \sum_h A_i A_{ih}^{ht} E_{hk}^{ht} C^{ht} T^{ht} \max_i (m_i)
\right)
$$
In this equation, the carbon emissions are divided into three parts: (1) Raw material emissions (RM_EF * mass of workpiece i). (2) Energy emissions from single-piece processing (E_EF * power of machine k used for workpiece i at process j * processing time). (3) Energy emissions from batch processing, which includes both energy (E_EF) and fuel (F_EF) components for melting and heat treatment processes. The variables include: RM_EF (raw material emission factor), m_i (mass of casting i), E_EF (energy emission factor), B_i (binary variable indicating if process j is single-piece), B_{ijk} (binary variable for workpiece i on machine k at process j), P_k (power of machine k), T_{ij} (processing time of workpiece i at process j), A_i (binary variable indicating if the process is a batch process), A_{ih}^m (binary variable for workpiece i assigned to melting batch h), E_{hk}^m (binary variable for melting batch h on machine k), T_m (melting time per unit mass), F_EF (fuel emission factor), A_{ih}^{ht} (binary variable for workpiece i in heat treatment batch h), C^{ht} (fuel consumption per unit time for heat treatment), and T^{ht} (heat treatment time per unit mass).
Constraints
Workpieces are subject to various constraints during production, and the optimized schedule must operate within these bounds. When forming batches, the capacity constraints of the melting furnace and heat treatment furnace must be respected, along with processing order and equipment availability.
- Machine Capacity Constraints: The total mass of workpieces in a batch must not exceed the machine’s maximum capacity and must meet its minimum load requirement.
$$ L_k^m \leq \sum_i A_i A_{ih}^m E_{hk}^m m_i \leq Q_k^m $$
$$ L_k^{ht} \leq \sum_i A_i A_{ih}^{ht} E_{hk}^{ht} m_i \leq Q_k^{ht} $$
where Lkm and Qkm are the minimum and maximum capacities of melting furnace k, respectively, and Lkht and Qkht are the corresponding values for the heat treatment furnace k.
- Machine Assignment Constraints:
$$ \sum_k B_i B_{ijk} = 1 $$
$$ \sum_h A_i A_{ih}^m E_{hk}^m = 1 $$
$$ \sum_h A_i A_{ih}^{ht} E_{hk}^{ht} = 1 $$
These ensure that, during a single-piece processing stage, a workpiece can only be processed on one machine at a time, and during a batch processing stage, a batch can only be processed on one specific machine.
- Process Order Constraint:
$$ TS_{ij} + T_{ij} = TE_{ij} $$
$$ TE_{ij} \leq TS_{i(j+1)} $$
This constraint ensures that the defined process sequence for the workpiece is maintained. TSij and TEij are the start and end times for workpiece i at process j, respectively.
Batch Grouping Rules for Sand Casting Foundries
To align with actual production scenarios in a sand casting foundry, it is necessary to formulate batch grouping rules for the melting and heat treatment processes. These rules aim to minimize the processing time of workpieces in these batch stages, thereby enhancing overall enterprise productivity. While the traditional “first-come-first-batched” strategy is simple to implement, it can lead to resource inefficiency. Therefore, we developed specific batch grouping rules based on our whole-process scheduling model.
Melting Process Batch Grouping Rules
Forming batches in the melting process requires considering several constraints, such as metal type and workpiece mass. Our rules for this stage are based on workpiece due dates and material properties.
- Due Date Priority: The priority for grouping is determined by the urgency of the workpiece’s due date. The remaining due date before the melting process is normalized to create a priority index di. A smaller Di indicates higher priority.
$$ d_i = \frac{\max(D_i) – D_i}{\max(D_i) – \min(D_i)} $$
- Melting Process Similarity: Workpieces with different material types cannot be placed in the same melting batch. We calculate a similarity index Sii’m between two workpieces i and i’, considering material compatibility (binary variable Xii’) and the standardized difference in pouring temperatures (tim).
$$ S_{ii’}^m = X_{ii’} \left( 1 – \frac{|t_i^m – t_{i’}^m|}{\max(t_i^m, t_{i’}^m)} \right) $$
The overall similarity of a melting batch h is then calculated as the average pairwise similarity:
$$ S_h^m = \frac{1}{n_h^m (n_h^m – 1)} \sum_i \sum_{i’} A_i A_{i’} A_{ih}^m A_{i’h}^m S_{ii’}^m $$
The Melting Batch Rationality Function, f1, is defined to maximize the weighted sum of batch similarity and due date priority:
$$ f_1 = \max \left( S_h^m \sum_i d_i A_i A_{ih}^m m_i \right) $$
Heat Treatment Process Batch Grouping Rules
The heat treatment process is a typical batch operation. When forming heat treatment batches, factors such as heat treatment type and workpiece mass must be considered. Our rules consider due dates, heat treatment similarity, and mass deviation.
- Due Date Priority: Similar to the melting process, the priority for heat treatment is based on the remaining due date.
$$ d_i = \frac{\max(D_i – \sum_j^{m-1} T_{ij}) – (D_i – \sum_j^{m-1} T_{ij})}{\max(D_i – \sum_j^{m-1} T_{ij}) – \min(D_i – \sum_j^{m-1} T_{ij})} $$
- Heat Treatment Similarity: The similarity between two workpieces for heat treatment, Sii’ht, depends on the compatibility of their cooling methods (Yii’) and the standardized difference in their holding temperatures (tiht).
$$ S_{ii’}^{ht} = Y_{ii’} \left( 1 – \frac{|t_i^{ht} – t_{i’}^{ht}|}{\max(t_i^{ht}, t_{i’}^{ht})} \right) $$
The batch similarity is then:
$$ S_h^{ht} = \frac{1}{n_h^{ht} (n_h^{ht} – 1)} \sum_i \sum_{i’} A_i A_{i’} A_{ih}^{ht} A_{i’h}^{ht} S_{ii’}^{ht} $$
- Minimizing Mass Deviation: In heat treatment, the processing time for a batch is determined by the workpiece with the largest mass. To minimize processing waste and potential quality issues like oxidation, the mass deviation within a batch should be minimized. We use the relative standard deviation (σhht) to define it.
$$ \sigma_h^{ht} = \frac{\sqrt{\frac{1}{n_h^{ht}} \sum_i \left( \sum_i A_i A_{ih}^{ht} m_i – \frac{1}{n_h^{ht}} \sum_i A_i A_{ih}^{ht} m_i \right)^2}}{\frac{1}{n_h^{ht}} \sum_i A_i A_{ih}^{ht} m_i} $$
The Heat Treatment Batch Rationality Function, f2, is then:
$$ f_2 = \max \left( \frac{S_h^{ht}}{\sigma_h^{ht}} \sum_i d_i A_i A_{ih}^{ht} m_i \right) $$
Model Solving and Numerical Verification
We employed the NSGA-III (Non-dominated Sorting Genetic Algorithm III) multi-objective optimization algorithm to solve the Batch-HFSP(Qm) model. Prior to implementing the algorithm, the batch grouping rules were applied to form batches for the melting and heat treatment processes. The algorithm then optimizes the processing sequence and machine assignment for all workpieces, including those within the formed batches.
Algorithm Implementation
The Batch-HFSP(Qm) model has three objective functions. After generating reasonable batch combinations based on our rules, the algorithm optimizes the processing order and machine selection to determine the final schedule. The NSGA-III algorithm flow is used for this purpose. A two-segment encoding scheme (process-machine) was adopted, where a gene consists of a process segment (determining the processing sequence of workpieces) and a machine assignment segment (determining the machine for each process for each workpiece). The gene length L is:
$$ L = 2 \times P \times N $$
where P is the total number of processes and N is the total number of workpieces. The process segment uses a repetition-based encoding, where the k-th occurrence of a workpiece number represents its k-th process.
Experimental Setup and Performance Metrics
To validate the model and compare the performance of different algorithms, we designed test cases based on data from a typical sand casting foundry, as summarized in the following table.
| Process | Number of Machines | Machine Power (kW) | Processing Time (h) |
|---|---|---|---|
| Molding | 3 | {20, 20, 36} | [5, 10] |
| Melting & Pouring | 4 | {80, 80, 100, 100} | NaN (batch-dependent) |
| Shakeout | 2 | {12, 36} | [2, 5] |
| Grinding | 4 | {36, 60, 90, 120} | [15, 30] |
| Cutting | 2 | {12, 16} | [2, 5] |
| Shot Blasting | 4 | {12, 16, 16, 36} | [5, 8] |
| Heat Treatment | 3 | {72, 72, 90} | NaN (batch-dependent) |
We designed three test cases with n ∈ {10, 20, 25} workpieces, with other parameters generated uniformly from given ranges. Each algorithm was run 10 times for 1000 generations for each test case. We used three standard metrics to compare the algorithms: Inverted Generational Distance (IGD, DIG), Spacing (SP, PS), and Hypervolume (HV, VH). The true Pareto front was formed by combining the non-dominated fronts from all algorithms run for 10,000 generations.
- IGD (DIG): Measures the average Euclidean distance from points in the true Pareto front to the nearest point in the algorithm’s approximated solution set. A smaller value indicates better convergence.
$$ D_{IG}(F, P^*) = \frac{1}{|P^*|} \sum_{y \in P^*} \min_{x \in F} d(y, x) $$
- SP (Ps): Measures the uniformity of distribution of the obtained solution set. A smaller value indicates a more uniform distribution.
$$ P_s = \sqrt{\frac{1}{n} \sum_{i}^{n} (d_i – \bar{d})^2} $$
- HV (VH): Measures the volume of the objective space covered by the solution set relative to a reference point. This is a comprehensive indicator of both convergence and distribution. A larger value is better.
$$ V_H(F, r) = V \left( \bigcup_{x \in F} [x, r] \right) $$
Results and Discussion
The comparative results of the algorithms on the three test cases are shown in the table below. The values represent the average of 10 independent runs.
| Algorithm | Metric | 10 Workpieces | 20 Workpieces | 25 Workpieces |
|---|---|---|---|---|
| NSGA-III (Our Work) | DIG | 0.1519 | 0.1766 | 0.2528 |
| PS | 0.0430 | 0.0542 | 0.0682 | |
| VH | 0.5503 | 0.5974 | 0.6015 | |
| NSGA-II | DIG | 0.1624 | 0.1983 | 0.2577 |
| PS | 0.0445 | 0.0543 | 0.0634 | |
| VH | 0.5450 | 0.5564 | 0.5542 | |
| MOEA/D | DIG | 0.3887 | 0.5770 | 0.9225 |
| PS | 0.0611 | 0.0780 | 0.0582 | |
| VH | 0.3240 | 0.1688 | 0.0909 | |
| SPEA2 | DIG | 0.1522 | 0.1797 | 0.2900 |
| PS | 0.0384 | 0.0452 | 0.0671 | |
| VH | 0.5488 | 0.5781 | 0.5548 | |
| SMS-EMOA | DIG | 0.1593 | 0.1799 | 0.2662 |
| PS | 0.0494 | 0.0500 | 0.0664 | |
| VH | 0.5353 | 0.5870 | 0.5529 |
The results clearly demonstrate the superiority of the NSGA-III algorithm for this problem, particularly as the problem size increases. For the 20-workpiece candidate pool, NSGA-III’s DIG is at least 1.72% lower and its VH is at least 1.78% higher than the other algorithms. For the 25-workpiece pool, the advantage is even more pronounced, with NSGA-III achieving at least a 1.90% lower DIG and at least an 8.42% higher VH. For the smaller 10-workpiece case, the performance differences were less significant. This confirms that NSGA-III, with its reference-point-based selection mechanism, is particularly effective for complex problems with a larger number of decision variables and a more intricate objective space. While SPEA2 showed competitive diversity (lowest PS in the 20-workpiece case), NSGA-III consistently provided the best trade-off between convergence and diversity, as reflected in the HV metric.
The Pareto frontier plots for one run of the 25-workpiece case further illustrate these findings. The frontiers clearly show the trade-off relationship between the three objectives. For instance, minimizing makespan (O1) often conflicts with minimizing the delivery penalty (O2) and minimizing carbon emissions (O3). The solutions obtained by NSGA-III are generally located on a dominant front compared to those from other algorithms, validating its effectiveness. A sample Gantt chart from a solution obtained by NSGA-III for a 20-workpiece case showed a makespan of 414 hours, carbon emissions of 183,379 kg, and a delivery penalty of 3,629 hours, demonstrating the practicality of the generated schedules.
Conclusions
- We successfully constructed a Batch-HFSP(Qm) model tailored for a sand casting foundry and used the NSGA-III algorithm for its solution. The model’s validity is confirmed through numerical experiments. By considering the batch processing nature of melting and heat treatment stages, and by formulating specific batch grouping rules, the proposed whole-process production scheduling solution effectively addresses the issues of resource waste and workpiece delays that often arise from experience-based scheduling in sand casting foundries. This approach can help enterprises improve production efficiency and reduce their carbon footprint.
- The research indicates that while NSGA-III demonstrates superior convergence and comprehensive performance, its performance in terms of the Spacing metric (PS) is not significantly better than other algorithms. This suggests that the uniformity of the population distribution could be a potential area for future improvement of the NSGA-III algorithm.
- Future work could extend the Batch-HFSP(Qm) model to incorporate more realistic constraints common in sand casting foundries, such as handling emergency orders and re-entrant processes, thereby making the scheduling system even more practical and robust.