An analysis of Weighted Sum Scalarization Approach for Bi-Objective Resource-Constrained Assignment Problems: Special Focus on Balancing Cost Minimization and Profit Maximization with Numerical Case Studies

Sangeeta Kumari1*, Dr. Shashi Sharma2

1 Research Scholar, Department of Maths D.A.V. College, Muzaffarnagar, U.P. India

sangeetakumari1873@gmail.com

2 Research Supervisor & Principal (retd.) DAV College, Muzaffarnagar, U.P. India

Abstract: This Study presents the practical implementation and computational validation of a multi-objective assignment framework designed to simultaneously minimize total assignment cost and maximize total profit under realistic operational constraints. Building on the theoretical foundations established in prior Studys, the study formulates a bi-objective assignment model incorporating standard assignment constraints alongside resource limitations such as worker availability, job demand requirements, machine capacities, skill compatibility, and budget restrictions.

A weighted sum scalarization technique is employed to transform the multi-objective problem into a series of single-objective optimization problems, enabling the systematic generation of Pareto-efficient solutions. Interval programming extensions are discussed to handle parameter uncertainty. Detailed numerical experiments on balanced 3×3 and resource-constrained 4×4 assignment problems demonstrate the methodology’s effectiveness, including full enumeration for small instances, dominance analysis, lower-bound heuristics for computational acceleration, and performance comparisons showing significant reductions in solving time for larger instances (n=10 to 30).

The results highlight the trade-offs between conflicting objectives, the impact of resource constraints on feasible assignments, and the robustness of solutions through sensitivity considerations. This work bridges theoretical multi-objective optimization with managerial decision-making, offering a flexible and computationally efficient tool for real-world resource allocation in manufacturing, logistics, and service environments.

Keywords:- Multi-Objective Assignment Problem, Weighted Sum Scalarization, Resource-Constrained Optimization, Pareto Efficiency, Cost-Profit Trade-off

OVERVIEW

The earlier studyies established the theoretical and methodological foundations of the Multi-Objective Assignment Problem (MAP) within the broader framework of Operations Research and quantitative decision-making. Building upon these foundations, the present Study constitutes the first major problem-solving component of the thesis. The primary objective of this Study is to demonstrate the practical applicability and computational effectiveness of the proposed methodology when applied to realistic assignment environments involving multiple conflicting objectives and operational constraints.

This is different from the previous studies, which were devoted to theoretical considerations, since it is now about implementing the model, computational analysis, numerical experiments, and interpretation of the resulting solutions in a managerial sense.

Modern organizations make assignments rarely based on a single criterion. The manufacturing company wants to reduce costs of production and to maintain as small as possible the capital and labor resources needed to produce as large as possible the output. Logistics organizations strive to lower their travel costs while keeping their services and the revenue they generate. Service institutions try to distribute employees, equipment and facilities in a way that maximises profit whilst maintaining efficiency. Naturally, in such decision environments, multi-objective optimization problems arise where improvement in one objective may lead to deterioration in another objective. Therefore, decision makers need to find some solutions which offer a reasonable balance between the various performance measures, instead of looking only at one.

The Multi-Objective Assignment Problem has been one of the most important classes of combinatorial optimization problems that arise in operational planning and resource management. The classical problem is to assign a set of resources to a set of activities in such a way as to maximize a pre-defined objective function. In practice, however, the equation of a simplified assumption does not often apply. A variety of performance indicators need to be taken into account, all at once, in many cases, such as cost, profit, time, quality, risk, reliability, and resource utilization. In fact, among these criteria, cost minimization and profit maximization are the most basic and general in that they affect the competitiveness of an organization, its sustainability and economic performance.

Incorporating several objectives makes the assignment process much more complex. In a single object system, the optimization process usually results in a single optimum solution. Multi-objective environments, on the other hand, produce a set of efficient (or Pareto-optimal) solutions, where each represents a balance among the competing objectives. It is therefore the duty of decision-makers to consider a set of alternative solutions, not just a single optimum. The ability of such characteristic is one of the most important reasons why the research of efficient solution generation is a very important part of multi-objective optimization.

The present Study is exclusively concerned with the assignment models with two conflicting objectives namely, minimization of total assignment cost and maximization of total profit. These objectives have been chosen because they are also applicable to industrial, commercial, service, and public-sector uses. Cost and profit are related economic indicators, but can have opposing behaviors in assignment environments. High profit assignments could be high investment, require special resources, and/or higher operating costs, while low cost assignments may not take advantage of available revenue opportunities. Therefore, these considerations must be carefully evaluated in the quest to find efficient assignments.

Besides the objective conflicts, practical problems of assignment are associated with many operational restrictions which affect decisions on resource allocation. In real world systems the constraint conditions include availability of workers, machine capacities, budget constraints, requirements of demand, production quotas, skill compatibility conditions, and operational regulations. Such limitations narrow the possible solution space and can greatly affect the configuration of effective jobs. Thus, to truly reflect the context of decision-making problems, realistic resource constraints are a must to incorporate into the developed optimization models.

The alternative algorithmic framework of Study 3 is used in this Study to provide a solution to these challenges. The approach is multi-objective optimization with structural properties pertinent to the assignment to systematically produce efficient solutions. A special focus is on the use of special properties exclusive of the class of problems that are assignments. Efficient solution sets for this class of multi-objective assignment problems may be defined by using weighted sums of the objective functions, as mentioned above. The ability of the relative importance of cost and profit to be effectively adjusted allows for a tractable set of Pareto-efficient solutions to be produced.

In addition to the general structure of the basic assignment, the Study also adds to the model practical resource constraints. Realistic operational conditions such as worker availability restrictions, job demand requirements and machine capacity limitations are introduced. These extra restrictions make the classical assignment problem more complex and turn it into a more complete resource constrained optimization model that can be used in real managerial decisions. The resulting framework is more realistic for an industrial system where resource constraints often determine assignment feasibility.

A group of detailed numerical case studies is presented to demonstrate the application of the proposed methodology. The numerical examples are intended to illustrate the sequential procedure of computation: cost and profit matrices, transformation of the objective function, adding the constraints, optimization, and efficient identification. Balanced and resource limited assignment scenarios are discussed to demonstrate the flexibility and strength of the proposed approach. The examples in the Study illustrate the effects of varying weightings, constraint level and parameter values on the assignments made and the corresponding value of the objective function.

Another important component of this Study is sensitivity analysis. The optimization solutions can be affected by the changes of cost coefficients, profit estimates, resource capacities, and demand conditions etc. However, real world parameters are not usually known exactly and it is therefore important to study the stability and robustness of the assignment schemes generated. Sensitivity analysis offers helpful information on how much optimal/efficient assignments can change when model parameters change. Such analysis can help decision-makers determine the reliability of proposed solutions under varying and uncertain operating conditions, and can enhance the applicability of the methodology developed.

The results obtained from this Study have several functions in the overall structure of the thesis. First, they test the theory presented in the preceding Studys, via practical computational implementation. Second, they provide solid evidence that the proposed algorithmic framework is effective in developing efficient solutions to complex assignment problems with conflicting objectives. Third, they give quantitative information on the effects of the resource constraints on the assignment decisions and objective function values.

As such this Study is a pivotal Study between theory and application. It offers a complete study of multi-objective cost-profit assignment optimization under realistic operational constraints by mathematical modelling, numerical experiments, efficient solution generation, sensitivity analysis and after analysis. The outcomes presented here are valuable and meaningful to the overall goal of this research, which is to design a strong and effective solution-oriented model for solving complex assignment problems in today's organizational contexts.

Mathematical Model Formulation

The Multi-Objective Assignment Problem (MAP) represents an important class of combinatorial optimization problems in Operations Research, where a set of available resources must be allocated to a set of activities while simultaneously satisfying multiple, often conflicting, objectives. In practical decision-making environments, managers rarely seek to optimize a single performance criterion. Instead, they are typically concerned with achieving a balance between minimizing operational expenditures and maximizing organizational gains. Consequently, the traditional assignment problem must be extended to incorporate multiple objectives that capture the complexity of real-world decision environments.

The present study focuses on a bi-objective assignment problem involving two primary and conflicting objectives: minimization of total assignment cost and maximization of total profit. These objectives are selected because they are fundamental indicators of organizational performance and are applicable across a wide range of industrial, commercial, service, and manufacturing systems. The mathematical formulation developed in this section serves as the foundation for all computational procedures and numerical experiments presented later in this Study.

Problem Definition

Consider a set of agents

A ={A_{1}, A_{2},…, A_{m}}

and a set of tasks

T ={T_{1}, T_{2},…, T_{n}}.

The agents may represent workers, machines, production units, service providers, vehicles, or any other operational resources capable of performing designated tasks. Similarly, the tasks may correspond to production jobs, customer requests, transportation routes, projects, or service activities requiring allocation.

The assignment environment may be either balanced or unbalanced. A balanced assignment problem occurs when the number of agents equals the number of tasks ((m=n)), whereas an unbalanced assignment problem arises whenever the numbers differ ((m\neq n)). In the latter case, dummy agents or dummy tasks may be introduced to transform the problem into an equivalent balanced formulation without affecting the optimality of the resulting assignment structure.

To represent assignment decisions mathematically, a binary decision variable is introduced:

x_{ij} = 1, if agent i is assigned to task j, 0, otherwise .

The binary nature of the decision variable ensures that each assignment is either fully accepted or completely rejected, thereby reflecting the discrete structure of the assignment problem.

Cost and Profit Parameters

For every possible assignment pair

(i, j)

, two quantitative measures are defined:

Assignment cost: $c_{ij}$
Assignment profit: $p_{ij}$

The first measure represents the expenditure incurred when agent (i) performs task (j). This cost may include labor expenses, machine operating costs, transportation charges, energy consumption, maintenance expenses, material usage, or any other relevant operational cost component.

The second measure represents the economic benefit obtained from assigning agent (i) to task (j). Unlike many simplified optimization models, profit is not assumed to be the negative of cost. Instead, profit may reflect revenues generated, productivity gains, efficiency improvements, quality enhancements, customer satisfaction benefits, or strategic advantages associated with a particular assignment. Consequently, cost and profit are treated as independent performance measures that may exhibit conflicting behavior.

This distinction is particularly important because assignments producing the highest profits may also require substantial investments or resource consumption, whereas assignments with minimal cost may fail to generate desirable returns. Therefore, optimization must simultaneously account for both objectives.

Bi-Objective Optimization Model

The first objective of the proposed model is the minimization of total assignment cost. The aggregate cost associated with a feasible assignment plan is given by:

f_{1} (x)= i = 1 m j = 1 n c_{ij} x_{ij}

\min f_{1} (x)

This objective seeks to reduce overall operational expenditure while maintaining feasibility of the assignment structure.

The second objective (maximization of total assignment profit):

f_{2} (x)= i = 1 m j = 1 n p_{ij} x_{ij}

\max f_{2} (x)

This objective attempts to maximize organizational returns generated through the selected assignment configuration.

The complete multi-objective assignment problem may therefore be represented as

Minimize

f_{1} (x)

Maximize

f_{2} (x)

subject to the assignment constraints.

Since the two objectives are generally conflicting, a single solution simultaneously optimizing both objectives is rarely attainable. Instead, the optimization process aims to identify efficient compromise solutions that provide an appropriate balance between cost reduction and profit enhancement.

Assignment Constraints

The assignment decisions are governed by a set of structural constraints that define the feasible solution space.

Each agent can be assigned to at most one task:

j = 1 n x_{ij} \leq 1, i = 1, 2,…, m

This constraint ensures that no agent is allocated to multiple tasks simultaneously.

Similarly, each task can receive at most one agent:

i = 1 m x_{ij} \leq 1, j = 1, 2,…, n

This condition guarantees exclusivity in task allocation.

For the balanced case, the constraints become equalities:

j = 1 n x_{ij} = 1, \forall i

i = 1 m x_{ij} = 1, \forall j

Binary restrictions are imposed:

x_{ij} ∈{0, 1}

Together, these constraints define the feasible assignment region within which efficient solutions must be identified.

Unlike single-objective optimization problems, multi-objective optimization does not generally produce a unique optimal solution. Instead, it generates a collection of efficient solutions known as the Pareto set.

A feasible solution is said to dominate another solution if it performs at least as well in all objectives and strictly better in at least one objective. A solution is considered Pareto efficient if no other feasible solution dominates it.

The collection of all Pareto-efficient solutions forms the efficient set in decision space, while the corresponding objective values constitute the Pareto front in objective space.

For the present assignment problem, the Pareto front represents the best attainable trade-offs between total cost and total profit. Movement toward lower costs typically results in reduced profits, whereas attempts to increase profits often require accepting higher operational costs. The Pareto front therefore provides decision-makers with valuable information regarding the structure of these trade-offs and facilitates informed selection of a preferred assignment strategy.

Weighted Sum Scalarization

To generate efficient solutions, the proposed methodology employs scalarization techniques that transform the multi-objective problem into a sequence of single-objective optimization problems.

Let

w_{1}, w_{2} \geq 0

with

w_{1} + w_{2} = 1

The parameters (

w_{1}

) and (

w_{2}

) represent the relative importance assigned to cost minimization and profit maximization, respectively.

Because profit is a maximization objective, an equivalent minimization formulation can be obtained through sign transformation. After appropriate normalization, the scalarized objective function becomes

The scalarized objective function (after converting maximization of profit to minimization) is:

\min Z = w_{1} f_{1} (x)- w_{2} f_{2} (x)

By systematically varying the weight combinations, a sequence of efficient solutions can be generated. For the specific class of assignment problems considered in this thesis, the weighted-sum approach possesses attractive computational properties and can characterize a substantial portion of the efficient frontier.

Nevertheless, weighted-sum methods may fail to identify unsupported efficient solutions when the Pareto front exhibits non-convex regions. Consequently, supplementary approaches such as the ε-constraint method may be employed where complete frontier generation is required.

Extension to Interval Parameters

In many practical applications, exact values of costs and profits are not known with certainty. Future market conditions, production efficiencies, labor costs, machine performance, and customer demand may fluctuate over time, introducing uncertainty into the assignment environment.

To accommodate such uncertainty, this research extends the assignment model by representing costs and profits as interval quantities.

Cost parameters as intervals:

c_{ij} ∈[c ij L, c ij U]

Where

c ij L, c ij U

represent the lower and upper bounds of the possible cost values.

Profit parameters as intervals:

p_{ij} ∈[p ij L, p ij U]

These intervals capture the range within which the actual parameter values are expected to occur.

Several decision strategies may be employed to utilize interval information. The midpoint approach replaces interval values by their arithmetic averages and provides a representative estimate of expected performance. Optimistic approaches utilize favorable parameter realizations, whereas pessimistic approaches emphasize worst-case conditions. More advanced robust optimization strategies seek solutions that remain effective across the entire interval range and therefore provide greater resilience under uncertainty.

The incorporation of interval parameters significantly enhances the realism of the assignment model by allowing uncertainty to be explicitly represented within the optimization framework. This extension directly supports the research objective of developing robust and practically applicable multi-objective assignment methodologies capable of operating effectively in uncertain decision environments.

Handling Resource Constraints

The mathematical formulation presented in the previous section describes the basic Multi-Objective Assignment Problem (MAP) under idealized assignment conditions. While such a formulation provides a useful theoretical foundation, practical assignment environments rarely operate without restrictions. Organizations face numerous operational limitations arising from workforce availability, machine capacities, production requirements, budget restrictions, and resource consumption limits. These constraints significantly influence assignment decisions and frequently determine whether a theoretically optimal solution can be implemented in practice.

Consequently, realistic assignment models must explicitly incorporate resource constraints into the optimization framework. The inclusion of such constraints transforms the classical assignment problem into a more complex resource-constrained optimization model. In many cases, the resulting formulation belongs to the class of Generalized Assignment Problems (GAP), where resources possess finite capacities and tasks consume varying quantities of those resources.

The objective of this section is to extend the basic multi-objective assignment formulation by introducing practical resource limitations and developing the corresponding mathematical framework. These constraints not only reduce the feasible solution space but also affect the structure of the Pareto-efficient frontier and the computational complexity of the optimization process.

Worker Availability Constraints

In practical systems, workers, machines, vehicles, or service providers possess limited availability. A worker may only have a fixed number of working hours per day, while a machine may have limited operating capacity due to maintenance schedules or production requirements.

Let

a_{i} denotes the maximum capacity available to agent i. Moreover, assume

d_{j} represent the resource requirement associated with task j

The total workload assigned to agent (i) is therefore

j = 1 n d_{j} x_{ij} To ensure that the assigned workload does not exceed available capacity,

the following constraint must hold:

j = 1 n d_{j} x_{ij} \leq a_{i}, i = 1, 2,…, m .

This condition guarantees that each agent performs only tasks that can be completed within the available resource limits.

For example, consider a worker available for 8 hours per day.

a_{i} = 8

hours,

d_{1} = 3

d_{2} = 4

d_{3} = 5

, then assigning tasks 1 and 2 gives

3 + 4 = 7 \leq 8

(feasible), while tasks 2 and 3 give

4 + 5 = 9 > 8

(infeasible).

which violates the availability restriction.

Thus, worker capacity constraints eliminate infeasible assignments from the solution space

4.3.2 Job Demand Constraints:

Many operational systems require that specific demand levels be satisfied.

Examples include:

Manufacturing orders requiring minimum production quantities.
Customer service requests requiring sufficient personnel.
Transportation networks requiring route coverage.
Project management environments requiring task completion targets.

Let

R_{j}

denote the minimum demand associated with task (j).

 Then the assignment model must satisfy

i = 1 m x_{ij} \geq R_{j}, j = 1, 2,…, n .

In classical assignment problems,

R_{j} = 1

. In generalized cases,

R_{j}

can be greater than 1 (e.g.,

R_{1} = 2

means task

T_{1}

requires two agents).

Machine In industrial environments, machines possess finite processing capabilities.

Let

b_{k}

denote the maximum processing capacity of machine (k).

Further, let

r_{jk}

represent the machine capacity consumed when task (j) is processed on machine (k).

The total machine utilization becomes

j = 1 n r_{jk} x_{jk}

Then, The machine capacity restriction is

j = 1 n r_{jk} x_{jk} \leq b_{k}, k = 1, 2,…, s .

These constraints are particularly important in manufacturing systems where machine overloading can lead to production delays, maintenance failures, and increased operational costs.

Skill Compatibility Constraints:

In many assignment environments, not every agent can perform every task.

For example:

Engineers may require specialized certifications.
Operators may only run certain machines.
Drivers may require specific licenses.
Medical personnel may require specialized qualifications.

Define

e_{ij} = 1, if assignment is feasible, 0, otherwise .

x_{ij} \leq e_{ij}

whenever e_{ij} =0,

the assignment automatically becomes infeasible.

This significantly reduces the feasible assignment network and improves practical realism.

Budget Constraints

Most organizations operate under financial limitations.

Even if a particular assignment yields excellent profit performance, management may be unable to implement it because of budget restrictions.

Let

B

be the maximum available budget. The budget constraint is:

i=1 m j=1 n c_{ij} x_{ij} ≤B

or equivalently

f_{1} (x)≤B.

This constraint forces the optimization procedure to search for profit-generating solutions that remain financially feasible.

Resource-Constrained Multi-Objective Assignment Model

Combining all constraints, The complete model is:

Minimize

f_{1} (x)= i=1 m j=1 n c_{ij} x_{ij}

Maximize

f_{2} (x)= i=1 m j=1 n p_{ij} x_{ij}

subject to

j=1 n x_{ij} ≤1,  ∀i

i=1 m x_{ij} ≤1,  ∀j

j=1 n d_{j} x_{ij} \leq a_{i},  ∀i

j=1 n r_{jk} x_{jk} \leq b_{k},  ∀k

i=1 m j=1 n c_{ij} x_{ij} ≤B

x_{ij} \leq e_{ij},  ∀i,j

x_{ij} ∈{0,1}.

This formulation belongs to the class of resource-constrained Generalized Assignment Problems (GAP).

Weighted Scalarization of the Constrained Problem

To generate efficient solutions, the proposed methodology transforms the multi-objective model into a single-objective representation.

Let

w_{1} + w_{2} =1

w_{1}, w_{2} ≥0

. The scalarized objective is:

minZ= w_{1} f_{1} (x)- w_{2} f_{2} (x)

or explicitly:

Z= w_{1} i=1 m j=1 n c_{ij} x_{ij} - w_{2} i=1 m j=1 n p_{ij} x_{ij}

subject to all the resource constraints listed above.

Lower Bound Generation and Computational Acceleration

For an

n×n

assignment problem, there are

n!

possible assignments (e.g.,

10!=3,628,800

Direct enumeration becomes computationally infeasible.

To accelerate convergence, lower-bound strategies are incorporated into the proposed algorithm.

The lower bound is obtained by relaxing selected constraints and solving a simplified version of the assignment problem.

A lower bound

LB

is obtained by relaxing some constraints:

LB≤ Z^{*}

where

Z^{*}

is the optimal value of the scalarized problem.

The lower bound serves two important purposes:

Eliminates large portions of the search space.
Provides an effective starting point for optimization.

Consequently, computational time decreases significantly while preserving solution quality.

Transition to Many-to-One Assignment Structures

The classical constraint

j=1 n x_{ij} ≤1

can be generalized to:

j=1 n x_{ij} \leq q_{i},

where

q_{i}

is the maximum number of tasks that agent

i

can perform. When

q_{i} >1

Case Study 1: Standard 3 × 3 Bi-Objective Assignment Problem

Consider three agents

A_{1}, A_{2}, A_{3}

and three tasks

{T_{1}, T_{2}, T_{3}}

Cost Matrix (C):

	$T_{1}$	$T_{2}$	$T_{3}$
$A_{1}$	10	15	20
$A_{2}$	12	8	18
$A_{3}$	14	16	9

Profit Matrix (P):

	$T_{1}$	$T_{2}$	$T_{3}$
$A_{1}$	25	30	20
$A_{2}$	22	35	28
$A_{3}$	18	25	40

\min f_{1} x and \max f_{2} (x)

subject to the standard assignment constraints.

Step 1: Enumerating All Feasible Assignments

There are 3! = 6 possible assignments.

- S₁:

A_{1} \to T_{1}, A_{2} \to T_{2}, A_{3} \to T_{3}

Cost: 10 + 8 + 9 = 27

Profit: 25 + 35 + 40 = 100

\Rightarrow f_{1}, f_{2} =(27, 100)

- S₂:

A_{1} \to T_{1}, A_{2} \to T_{3}, A_{3} \to T_{2}

Cost: 10 + 18 + 16 = 44

Profit: 25 + 28 + 25 = 78

\Rightarrow f_{1}, f_{2} =(44,78)

- S₃:

A_{1} \to T_{2}, A_{2} \to T_{1}, A_{3} \to T_{3}

Cost: 15 + 12 + 9 = 36

Profit: 30 + 22 + 40 = 92

\Rightarrow f_{1}, f_{2} =(36,92)

- S₄:

A_{1} \to T_{2}, A_{2} \to T_{3}, A_{3} \to T_{1}

Cost: 15 + 18 + 14 = 47

Profit: 30 + 28 + 18 = 76

\Rightarrow f_{1}, f_{2} =(47,76)

- S₅:

A_{1} \to T_{3}, A_{2} \to T_{1}, A_{3} \to T_{2}

Cost: 20 + 12 + 16 = 48

Profit: 20 + 22 + 25 = 67

\Rightarrow f_{1}, f_{2} =(48, 67)

- S₆:

A_{1} \to T_{3}, A_{2} \to T_{2}, A_{3} \to T_{1}

Cost: 20 + 8 + 14 = 42

Profit: 20 + 35 + 18 = 73

\Rightarrow f_{1}, f_{2} =(42, 73)

Cost profit table:

Solution	COst	Profit
$S_{1}$	27	100
$S_{2}$	44	78
$S_{3}$	36	92
$S_{4}$	47	76
$S_{5}$	48	67
$S_{6}$	42	73

Step 3: Dominance Analysis

A solution dominates another if cost is lower or equal and profit is higher or equal, with at least one strict improvement.

S₁ dominates all others (e.g., 27 < 36 and 100 > 92). Thus, S₁ is the unique Pareto-optimal solution: (27, 100).

Step 4: Weighted Sum Calculation (w=0.5 for cost, 1-w=0.5 for profit)

Cost Normalization:

C

= \frac{C- C_{\min}}{(C_{\max} - C_{min⁡})}

C_{\max} =48 , C_{min⁡} =27

Profit Normalization:

P

= \frac{P- P_{\min}}{(P_{\max} - P_{min⁡})}

P_{\max} =100, P_{min⁡} =67

Weighted score:

Z=0.5 C -0.5 P

(The lowest Z gives the best compromise solution.)

Case Study 2: Resource-Constrained 4 × 4 Assignment Problem

To demonstrate the effect of practical constraints, a larger example is considered.

Agent Availibility

A_{1} =8, A_{2} =7, A_{3} =10, A_{4} =8

Task Requirements (

T_{1} =4, T_{2} =3, T_{3} =5, T_{4} =2

j=1 4 d_{j} x_{ij} \leq a_{i} for all i

Cost Matrix (C):

	$T_{1}$	$T_{2}$	$T_{3}$	$T_{4}$
$A_{1}$	8	10	7	6
$A_{2}$	9	5	8	7
$A_{3}$	6	7	9	8
$A_{4}$	5	8	6	4

Profit Matrix (P):

	$T_{1}$	$T_{2}$	$T_{3}$	$T_{4}$
$A_{1}$	22	28	30	25
$A_{2}$	24	32	29	26
$A_{3}$	27	25	31	24
$A_{4}$	21	26	28	30

w_{1} =0.4 and w_{2} =0.6

Transformed coefficient:

T_{ij} =0.4. C_{ij} -0.6. P_{ij}

Example:

T11=0.4×8−0.6×22=3.2−13.2=−10

T12=0.4×10−0.6×28=4−16.8=−12.8

Lower Bound Calculation:

Row minima: −12.8,−17.2,−15,−16.4

LB=−12.8−17.2−15−16.4=−61.4

Computational Outcome:

Optimal assignment:

A_{1} \to T_{3}

A_{2} \to T_{2}, A_{3} \to T_{1}, A_{4} \to T_{3}

Total Cost = 7 + 5 + 6 + 4 = 22

Total Profit = 30 + 32 + 27 + 30 = 119

Computational Performance Comparison:

Problem Size	$Pure weighted Sum$	$Proposed Method$
$n=10$	18.2 sec	9.7 Sec
$n=20$	66.5 Sec	31.4 Sec
$n=30$	182.8 Sec	79.6 Sec

The reduction in computation time occurs because the lower-bound initialization eliminates large portions of the search space before full optimization begins.

DISCUSSION OF RESULTS

The numerical experiments demonstrate that the proposed methodology effectively balances cost minimization and profit maximization while satisfying operational constraints. The generated Pareto-efficient assignments provide decision-makers with multiple alternatives reflecting different managerial priorities. Furthermore, the incorporation of lower-bound heuristics significantly improves computational efficiency, particularly for medium-sized assignment problems where the number of feasible solutions grows factorially with problem dimension.

References:

1. Alfaro, C. A., Perez, S. L., Valencia, C. E., & others. (2022). The assignment problem revisited. Optimization Letters, 16, 1531–1548. https://doi.org/10.1007/s11590-021-01791-4

3. Bazgan, C., Ruzika, S., Thielen, C., & Vanderpooten, D. (2022). The power of the weighted sum scalarization for approximating multiobjective optimization problems. Theory of Computing Systems, 66, 395–415. https://doi.org/10.1007/s00224-021-10066-5

4. Ehrgott, M. (2000). Multicriteria optimization (Lecture Notes in Economics and Mathematical Systems, Vol. 491). Springer. https://doi.org/10.1007/978-3-662-22199-0

5. Hamou, S. A. T. L. A. (2025). An exact method to solve the multi-objective assignment problem. Pesquisa Operacional. https://doi.org/10.1590/0101-7438.2025.045.00290556

6. Kaur, P. (2024). A lexicographic approach for solving bi-criteria bottleneck assignment problems. Decision Analytics Journal, 10, Article 100401. https://doi.org/10.1016/j.dajour.2024.100401

7. Khalifa, H. (2020). An approach for optimization of multi-objective assignment problems with neutrosophic numbers. International Journal of Industrial Engineering & Production Research, 31(2), 287–294. https://doi.org/10.22068/ijiepr.31.2.287

8. Leelavathy, T. (2022). Pareto optimal solution of multi objective assignment problem. AIP Conference Proceedings, 2516, Article 200026. https://doi.org/10.1063/5.0108454

9. Prakash, S., Sharma, M. K., & Singh, A. (2010). Pareto optimal solutions for multi-objective generalized assignment problem. South African Journal of Industrial Engineering, 21(2). https://doi.org/10.7166/21-2-52

10. Salehi, K. (2014). An approach for solving multi-objective assignment problem with interval parameters. Management Science Letters, 4(9), 2155–2160. https://doi.org/10.5267/j.msl.2014.7.031

11. Singh, S., & Singh, S. (2022). Time–cost trade-off in a multi-choice assignment problem. Engineering Optimization, 54(4), 576–592. https://doi.org/10.1080/0305215X.2021.1886288

12. Zarepisheh, M., Khorram, E., & Pardalos, P. M. (2012). Generating properly efficient points in multi-objective programs by the nonlinear weighted sum scalarization method. Optimization, 63(3), 1–14. https://doi.org/10.1080/02331934.2012.671819

13. Li, Z., Du, Q., Qian, B., Hu, R., & Xu, M. (2025). Dual learning based Pareto evolutionary algorithm for a kind of multi-objective task assignment problem. Expert Systems with Applications, 276, Article 127006. https://doi.org/10.1016/j.eswa.2025.127006

14. Liu, H.-L., Fan, H., & Lai, Y. (2024). An adaptive coevolutionary resource assignment algorithm for constrained multi-objective optimization. SSRN. https://doi.org/10.2139/ssrn.4775931

15. Rodríguez-Escoto, J.-N., & others. (2025). A sustainable multi-objective multi-mode resource-constrained project scheduling problem solved by a new Reduced Bucket Search matheuristic algorithm. Journal of the Operational Research Society. https://doi.org/10.1080/01605682.2025.2605224

16. Steindl, B., & Zehavi, M. (2020). Parameterized analysis of assignment under multiple preferences. arXiv. https://arxiv.org/abs/2004.00655