Content area
This paper presents mathematical formulations to an application observed at an electronics manufacturer. After assembly, the electronic products are subjected to different accelerated tests using Batch Processing Machines (BPMs) arranged in a flow shop. A BPM can process several jobs simultaneously. When forming batches, the total size of all the jobs contained in a batch cannot exceed the machine capacity. The configuration of the batch affects the batch processing time and its due date. Due to the nature of the test conducted, the jobs cannot wait for more than a certain amount of time between two machines. The objective is to minimize the makespan and the maximum tardiness. The processing times, due dates, and sizes of the jobs are given. The capacity of the BPMs is known. This paper presents a weighted sum and a goal programming formulations of the problem under study. Heuristics were also developed. An experimental study compares the different formulations, and the heuristics based on solution quality and run time.
Abstract
This paper presents mathematical formulations to an application observed at an electronics manufacturer. After assembly, the electronic products are subjected to different accelerated tests using Batch Processing Machines (BPMs) arranged in a flow shop. A BPM can process several jobs simultaneously. When forming batches, the total size of all the jobs contained in a batch cannot exceed the machine capacity. The configuration of the batch affects the batch processing time and its due date. Due to the nature of the test conducted, the jobs cannot wait for more than a certain amount of time between two machines. The objective is to minimize the makespan and the maximum tardiness. The processing times, due dates, and sizes of the jobs are given. The capacity of the BPMs is known. This paper presents a weighted sum and a goal programming formulations of the problem under study. Heuristics were also developed. An experimental study compares the different formulations, and the heuristics based on solution quality and run time.
Keywords
Batch processing machines, flow shop, waiting time constraints, makespan, maximum tardiness.
(ProQuest: ... denotes formulae omitted.)
1. Introduction
This research was based on an application observed at an electronics manufacturer. Printed Circuit Boards (PCBs) used in different applications (e.g. notebooks, handheld devices, servers, etc.) are manufactured at this facility. After the PCBs are assembled, they are subjected to a couple of accelerated tests to identify any failures. The testing machines can test several PCBs simultaneously. Hence, these machines are referred to as Batch Processing Machines (BPMs). The job of a scheduler is to group the PCBs into batches and schedule them on the BPMs. The two BPMs are arranged in a flow shop environment and each PCB must be tested on these machines sequentially. The minimum testing times of the PCBs are predefined by the customer. When the PCBs are batched, the testing (or processing) time of the batch is determined by the longest testing time of the PCB in that batch. The due date of the batch is determined the earliest due date of all the jobs in that batch. Testing each PCB sequentially is time consuming and less efficient. Although a customer may not pay for the additional time required to test a PCB, from an operational perspective batching helps to minimize the time required to process all the PCBs.
The physical space available in the machine limits the batch size. Hence, when PCBs are batched the total size of all the PCBs in a batch should not exceed the machine capacity. In the two-stage flow shop considered, the batch composition cannot be changed between the two stages. Changing the composition is time consuming and functionally impossible. Additionally, the batches cannot wait for more than a predetermined time between the two stages of testing. In our study, the first stage of testing includes thermal cycling where the temperature of the PCB is cycled between high and low temperatures for a certain number of cycles. The second stage requires the PCB at a certain temperature to being the test. Hence, excessive cooling between the two stages will affect the second test procedure and is not permitted. This restriction is considered by placing a waiting time constraint between the two stages of testing. To improve customer satisfaction, the manufacturer also strives to complete all their orders by their due dates. However, this is not always possible. To gain operational efficiency the PCBs are batched, however, batching can delay the completion time and tardiness of some of the PCBs in a batch. Hence, the objective of the scheduler is to complete testing all the batches in the least time (i.e. minimize makespan or the completion time of the last batch) and minimize the maximum tardiness. All the PCBs in a batch begin and end their testing at the same time on each of the BPMs. Once the test begins, no new PCBs can be added or removed from the batch.
The scheduler is required to make two decisions: forming the batches and scheduling the batches. The batch formation affects the testing times on each machine. Hence, the completion times and the tardiness of the batches as well. Hence, these two decisions are interdependent and complex for a human to make optimal decisions. The objective of this study is to develop mathematical models to help the decision maker to form batches and schedule them on the two BPMs, so that the makespan and maximum tardiness is minimized. It is evident from this experimental study that solving mathematical formulations is time consuming and, in many cases, does not yield a feasible solution. Consequently, heuristics are also developed and experimented with. The testing machines are referred to as BPMs and the PCBs as jobs hereafter. The testing times are also referred to as processing times in the reminder of the paper.
Formally the problem under study can be described as follows. Given n jobs and their processing times, due dates, and sizes, the objective is to schedule these jobs on a two-stage flow shop so that the makespan and maximum tardiness is minimized. The two stages consist of one BPM each. Each BPM can process several jobs simultaneously if the total size of all the jobs in the batch does not exceed the machine capacity. The capacity of the two machines can be different. However, the composition of the batch should remain unchanged between the two stages. Hence, the machine with the least capacity dominates the batch forming decision. The manufacturer makes every effort to prevent an imbalance in capacity between the two machines. So, in this study we assume the two machines are of equal capacity. However, this is not a limiting assumption. In our mathematical model, the machine capacity can be restricted to the least capacity machine. The maximum waiting time allowed between the two stages is given.
2. Literature Review
Literature has numerous articles on scheduling discrete processing machines. However, the literature on scheduling batch processing machines is still limited. Refer to [1] for an overview of batching and scheduling problems. Batch processing machine scheduling problems can be classified into problems with constant batch processing time and varying batch processing time. In varying batch processing time problems, the processing time of a batch depends on the jobs that constitute a batch. On the other hand, in constant batch processing time problems, batch processing times are independent of these jobs. This paper deals with the varying batch-processing time scenario.
Damodaran and Srihari [2] proposed two mixed-integer linear programming formulations for a two-stage flow shop with BPMs in each stage. Liao and Liao [3] improved the formulation proposed in [2]. However, in [1] and [2] the waiting time constraints were not considered. Fu et al. [4] proposed a formulation in which the buffer space between two machines were considered. The number of jobs that could wait between the two stages was a constraint, but the waiting time was not considered. Klemmt and Monch [5] considered the waiting time between machines, however, they did not consider batching. Yugma et al. [6] proposed a formulation for batching and sequencing with a limited time window between two machines. Several heuristics were proposed. Nepal et al. [7] considered a problem like the one studied in this research; however, they considered only the makespan objective. This paper is different from [6] in that sense it considers varying job sizes, and the batch processing time depends on the longest processing job.
3. Model Formulation
This research considered two formulations for the bi-objective problem under study. The first formulation (Model WS) scalarized the two objective functions (i.e. makespan and maximum tardiness) by using the weighted sum of the two objectives. The second formulation (Model GP) is based off the goal programming approach. The notation used in mathematical formulation is presented below:
Sets
{j ε J} set of jobs
{k ε K} set of batches or positions
{m ε M} set of machines
Parameters
Pjm processing time of job j on machine m
Sj size of job j
dj due date of job j
Sm capacity of machine m
θ maximum waiting time allowed between the two stages
Decision Variables
Xjk 1, if job j is processed in kth batch/position on each machine; 0, otherwise
Qkm processing time of the kth batch on machine m
Ckm completion time of the kth batch on machine m
Cmax makespan or completion time of the last batch
Tmax maximum tardiness
Wk waiting time of the kth batch between the two stages
bk waiting time between kth and (k+1)st batch on stage 1
Tk tardiness of the kth batch
The two objectives are scalarized in the weighted sum method. Each objective is multiplied with a user assigned weight a, where a is between 0 and 1, to obtain a linear objective function as shown in (1).
... (1)
... (2)
... (3)
... (4)
... (5)
... (6)
... (7)
... (8)
... (9)
... (10)
... (11)
... (12)
... (13)
... (14)
... (15)
... (16)
Objective (1) minimizes the makespan. Constraint (2) ensures that each job is assigned to only one position or a batch. As the BPMs can process several jobs simultaneously, there can be more than one job assigned to a batch. Constraint (3) ensures that the size of the machine is not exceeded. The batch composition should not change between the two stages. Hence, the machine with the smallest capacity limits the batches formed. For a batch processing machine, the processing time is given by the maximum processing time of all the jobs in the batch. This is ensured by constraint (4). Constraint (5) determines the completion time of batch on machine 1. Constraint (6) determines the completion time of the first batch on machine 2. Constraint (7) determines the completion time of ťh batch on machine 2. Constraints (8) and (10) limit the waiting time for ťh batch between machine 1 and machine 2. Constraint (9) determines the tardiness of the batch. Constraint (11) determines the makespan. Constraint (12) determines the maximum tardiness. If none of the jobs are processed simultaneously, then the number of batches will be equal to the number of jobs considered in an instance. Hence, the maximum number of batches for a problem instance is known. Constraints (13), (15), and (16) enforce the non-negativity restrictions on the variables. Constraint (14) enforces the binary restriction on decision variable X. The second formulation is based off the goal programming approach. Under achievement ( C^ax, Tmax) and over achievement (C^ax, T^ax) variables are introduced in the formulation. The targets for Cmax and Tmax were set at zero.
... (17)
... (18)
... (19)
... (20)
Constraints (11) and (12) from Model WS are modified by including the underachievement and overachievement variables. IBM ILOG CPLEX 12.8 was used to solve the formulations for randomly generated problem instances on a PC with 13th gen intel i7 processor and 32GB RAM. Figure 1 shows a sample Pareto front solution for a 20-job instance. Scheduling a single BPM with makespan objective is NP-hard [8]. Consequently, the problem under study is also NP-hard. The run time required to solve 20 or more job instances is prohibitively large (see section 5). As the solver does not return feasible solutions even after running for several hours, heuristics were also proposed.
4. Heuristics
Batching is very similar to the bin packing problem. So, popular bin packing heuristics such as the Next Fit and First Fit were adopted to form the batches. Once the batches are formed, Johnson's algorithm can be applied (treating each batch as a job) to determine the batch sequence.
The Next Fit (FF) heuristic can be described as follows [9]:
1. Sequence the jobs randomly or by following any dispatching rule.
2. Select the job at the top of the list and place it in the current batch that is open, keeping in mind the capacity restriction. If the job does not fit in the current batch, create a new batch, and close the current batch. Repeat Step 2 until all the jobs have been assigned to a batch.
The First Fit (FF) heuristic can be described as follows [9]:
1. Sequence the jobs randomly or by following any dispatching rule.
2. Select the job at the top of the list and place it in the first batch that is open, keeping in mind the capacity restriction. If the job does not fit in any one of the existing batches, create a new batch. Whenever a batch is filled, then close the batch. Repeat Step 2 until all the jobs have been assigned to a batch.
The Johnson's algorithm for a two-stage flow shop [10]:
1. Form set 1 containing all the batches with gki < Ök2, where 0ki and 0k2 are the processing times of the batch on machines 1 and 2, respectively.
2. Form set 2 containing all the batches with 0ki > ßk2. The jobs with 0ki= Ök2 can be in either set 1 or set 2.
3. Form the sequence as follows:
a. The batches in set 1 go first in the sequence and they go in increasing order of Qd (SPT).
b. The batches in set 2 follow the batches in set 1 in decreasing order of 0k2 (LPT).
The heuristic to schedule jobs in a two-stage flow shops with batch processing machines in each stage:
1. Apply Johnson's algorithm to sequence the jobs using the job processing times.
2. Apply NF or FF to the job sequence obtained in step 1 to form the batches. Find the batch processing times and batch due dates.
3. Apply Johnson's algorithm to determine the SPT(1)-LPT(2) sequence using the batch processing times.
4. Schedule the first batch (say к = 1) from the sequence on both the machines and compute the total completion times on both the machines (i.e. TC\ and TC2, respectively). Determine the tardiness of the batch (Tk = TC2 - min dyj e k). Set Tmax = Tk.
5. Consider the next job (say j) from the SPT(1)-LPT(2) sequence,
a. if TC2 - ÇQy + TCi) < 6 (where 6 is the allowed waiting time), then schedule job j to begin its operation on machine 1 at TC\. Update TC\ = Qy + TC\ and TC2 = 0j2 + TC2.
b. Else, schedule job j to begin its operation on machine 1 at TC2 - Qy - 6. Update TC\ = TC2 - 6 andTC2= Й2 + ТС2.
c. Determine the tardiness of the batch (Tk = TC2 - min dyj e k). Set Tmax = Tk.
d. Go to step 4 until all the jobs are scheduled.
6. Cmax = TC2.
The heuristics were referred to as JRFFJR and JRNFJR in the rest of the paper. JRFFJR is to indicate that the jobs were first sequenced by Johnson's algorithm, then the FF heuristic was used to form the batches, and later Johnson's algorithm is used for sequencing the batches. The heuristics were implemented in Python. The solution from the heuristics were later compared with the solutions obtained from the commercial solver.
5. Experimental Study
Random data sets were generated to experiment with the formulations presented in section 3. Table 1 shows the logic followed to generate the data. Thirty random 10, 20, and 50-job instances were generated. Each instance was solved using the solver for five different values of weights. Altogether 150 experimental runs were carried out. The run time required by the solver to solve the models, and the objective function was recorded for each experimental run.
The solver took less than 3.31 seconds to solve each 1 О-job instance (see Table 2). However, the solver did not converge to an optimum even after running for several hours for many of the 20 and 50-job instances. Hence, the solver was allowed to run for 1800 seconds, and the best reported solution was used for comparison purposes. The run time required to solve Model GP was slightly better than Model WS. The commercial solver could not report a feasible solution on 23 50-job instances for Model WS and on 22 50-job instances for Model GP. The %GAP (between the best-known solution and linear solution) increases as the number of jobs increases, confirming longer run times needed to converge to an optimal solution. The % improvement in objective value between the two models were computed using (21). For all 10 job instances, both the models reported the same results. However, in 20-job instances Model WS on average reported an objective value that is 11.11% better than Model GP. Model WS reported a better solution in 12 instances (see Table 2). Model GP reported on an average 18.27% improvement in objective value on 5 of the 20 job instances.
% improvement = 100(Model WSObj - Model GPObj)/Model WSObj (21)
Table 3 compares the objective values (optimum for 10 job instances and best-known solution for 20 and 50 job instances after running the solver for 1800 seconds) obtained from the two models and the heuristics. The objective value obtained for all 10 job instances from the two models was the same. Model WS was better than Model GP on 15.3% of the instances. Model GP was better than Model WS on 8% of the instances. As the problem size increases JRFFJR performed better than JRNFJR. JRFFJR also performed slightly better than JRNFJR heuristics when the weighted sum of objection functions from the solver were compared with. On average the run time for the heuristics was less than one tenth of a second for each instance.
6. Conclusions
This research considered the machine scheduling problem observed at an electronics manufacturer. A two-stage flow shop with limited waiting time constraint was considered. The objective was to minimize makespan and maximum tardiness. This research proposed two formulations: (1) a linear scalarization of the two objectives as weighted sum, and (2) a goal programming formulation. Random problem instances were generated to understand the efficacy in solving the two formulations. A commercial solver was used to solve both the formulations. Both the models were effective in reporting the optimal solution in less than 3.31 seconds for all 10 job instances. However, both the models required longer run time to solve instances with 20 and 50-jobs. The weighted sum formulation was slightly better than the goal programing formulation. It was able to report a better solution on 15.3% of the instances. The goal programming formulation was better on 8% of the instances. The heuristics proposed were effective in finding a better solution than the solver on 16% of the instances. This research will continue to explore decomposition techniques as the models exhibit a block diagonal structure. The decomposition algorithm can help reduce the run time and improve the solution quality. The heuristics can serve as an initial solution to mcta-hcuristics such as simulated annealing, genetic algorithm, etc. The different approaches proposed can also be compared using other multi-objective metrics.
References
[1] J.W. Fowler, L. Monch, "A Survey of Scheduling With Parallel Batch (p-batch) Processing," European Journal of Operational Research, vol. 298, pp. 1-24, 2022.
[2] P. Damodaran and K. Srihari, "Mixed Integer Formulation to Minimize Makespan in a Flow Shop with Batch Processing Machine," Mathematical and Computer Modeling, vol. 40, no. 13, pp. 1465-1472, 2004.
[3] C.-J. Liao and L.-M. Liao, "Improved MILP models for two-machine flowshop with batch processing machines," Mathematical and Computer Modeling, vol. 40, no. 7-8, pp. 1254-1264, 2008.
[4] Q. Fu, A. I. Sivakumar and K. Li, "Optimisation of flow-shop scheduling with batch processor and limited buffer," International Journal of Production Research, vol. 50, no. 8, pp. 2267-2285, 2012.
[5] A. Klemmt and L. Mönch, "Scheduling jobs with time constraints between consecutive process steps in semiconductor manufacturing," in Proceedings of the 2012 Winter Simulation Conference (WSC), Berlin, 2012.
[6] C. Yugma, S. Dauzère-Pérès, C. Atrigues, A. Derreumaux and O. Sibille, "A batching and scheduling algorithm for the diffusion area in semiconductor manufacturing," International Journal of Production Research, vol. 50, no. 8, pp. 2118-2132, 2012.
[7] S. Nepal, S. Muthuswamy and P. Damodaran, "Scheduling Batch Processing Machines in a Flow Shop with Limited Waiting Time Constraints," Proceedings of the USE Annual Conference & Expo 2024, Montreal, CA.
[8] S. Mclouk, P. Damodaran, P.Y. Chang, "Minimizing makespan for a single machine batch processing with nonidcntical job sizes using simulated annealing," International Journal of Production Research, 87(2), 141-147, 2004.
[9] D. S. Johnson, "Near-Optimal Bin Packing Algorithm," Ph.D. dissertation, Amherst College, Massachusetts Institute of Technology, Amherst, 1968.
[10] K. R. Baker and D. Trietsch, Principles of Sequencing and Scheduling, 2nd ed., John Wiley & Sons, Inc., 2019.
Copyright Institute of Industrial and Systems Engineers (IISE) 2025