In today's competitive environment, manufacturing systems with a variety of product lines and product types, frequent switches, and the lack of systematic setup planning cause major resource inefficiencies. Setup times mainly depend on product and process characteristics, and it can be either sequence-independent or sequence-dependent. In this study, the sequence-dependent setup time (SDST) problem is considered to minimize the total setup time with sequencing setups to increase operational effectiveness and preserve competitiveness. The battery manufacturing process presents a highly relevant environment for studying and optimizing this problem. The production of batteries involves various technical constraints where the setup times between different product types is significantly influenced by the preceding task.A mixed-integer programming model is created using GAMS and solved using CPLEX. Although the model produces optimal solutions, as problem sizes increase, its computational efficiency significantly decreases, thus limiting its use in large-scale or time-sensitive production scenarios. To overcome this limitation, two heuristic algorithms—random search and greedy heuristic—are proposed. The random search explores the solution space through repeated random permutations, generating diverse feasible solutions within short computational times. The greedy heuristic iteratively constructs solutions by sequencing jobs with the minimum consecutive setup time; however, it does not always produce the global optimum solution. Computational experiments were conducted on different data sets with various initial conditions. The performance of the heuristics is evaluated by comparing with the CPLEX solutions, and the results show that heuristic methods significantly reduce computation time while achieving satisfactory solution quality.

Keywords

Job Sequencing, Mixed-Integer Programming (MIP), Optimization Models, Operational Efficiency, Production Improvement