An analysis of Problem Solving II – Advanced Assignment Variants

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: The evolution of modern manufacturing and logistics systems requires advanced mathematical frameworks capable of handling complex resource allocation challenges. This study investigates multi-objective, many-to-one generalized assignment problems characterized by constrained resource capacities, parameter uncertainties, and conflicting operational goals, including cost minimization, profit maximization, and makespan reduction. To mitigate the exponential computational complexity inherent in these NP-hard formulations, a hybrid optimization framework is proposed that integrates linear relaxations, greedy heuristics, Lagrangian relaxation, and scalarization-based techniques to establish robust lower-bound strategies. Numerical case studies involving interval-valued data demonstrate that the proposed approach substantially accelerates convergence rates and reduces search effort while generating stable, high-quality Pareto-optimal trade-offs. Ultimately, this framework provides a comprehensive, computationally efficient solution for realistic resource scheduling under shifting operational conditions.

Keywords: Multi-objective optimization, Generalized assignment problem, Heuristic lower bounds, Lagrangian relaxation, Pareto efficiency

OVERVIEW

The importance of studying many-to-one assignment structures has increased substantially with the growth of modern manufacturing systems, supply chain networks, service industries, healthcare scheduling, cloud computing environments, and transportation systems. In manufacturing environments, for example, a machine often processes multiple production orders within a planning horizon. Similarly, in logistics operations, distribution centers serve multiple customers while operating under capacity constraints. In workforce scheduling, employees are frequently assigned multiple tasks according to their skills, availability, and workload capacities. These scenarios cannot be adequately represented by conventional assignment formulations and therefore require more sophisticated optimization models.

Another important characteristic of contemporary decision-making environments is the existence of multiple conflicting objectives. Organizations rarely optimize a single performance measure. Instead, managers seek solutions that simultaneously minimize operational costs, maximize profits or revenues, reduce completion times, improve resource utilization, and enhance service quality. These objectives are often contradictory in nature. For instance, increasing profitability may require allocating jobs to highly productive but expensive resources, whereas minimizing costs may lead to longer processing times or reduced service levels. Consequently, decision-makers are interested not in a single optimal solution but rather in a set of efficient or Pareto-optimal solutions that provide different trade-offs among competing objectives. The multi-objective perspective adopted throughout this thesis is therefore particularly relevant for generalized assignment problems.

The extension from one-to-one assignments to many-to-one assignments introduces several new challenges. Capacity restrictions create additional feasibility considerations because each resource can only accommodate a limited amount of workload. The resulting optimization model becomes significantly more complex, particularly when multiple objectives are considered simultaneously. Furthermore, the inclusion of practical performance measures such as makespan, workload balancing, and capacity utilization often introduces nonlinear relationships into the mathematical formulation. These complexities make the direct application of traditional optimization techniques increasingly difficult, especially for medium- and large-scale problem instances.

To address these challenges, this chapter investigates advanced mathematical formulations and solution methodologies specifically designed for multi-objective generalized assignment problems. Particular emphasis is placed on the development and utilization of heuristic lower-bound strategies that can effectively guide the search process toward high-quality solutions. Lower bounds play a crucial role in optimization because they provide valuable information about the structure of the feasible solution space and help identify promising regions for further exploration. By generating strong initial estimates, lower-bound techniques can substantially reduce computational effort, improve convergence rates, and enhance the quality of the resulting Pareto approximations.

The study also examines the integration of lower-bound mechanisms with scalarization-based optimization approaches. Methods such as weighted-sum formulations and ε-constraint techniques are widely employed for generating Pareto-optimal solutions in multi-objective optimization. However, their effectiveness often depends on the quality of the initial search points and the efficiency of the exploration strategy. By incorporating heuristic and relaxation-based lower bounds, the proposed framework aims to accelerate the search process while maintaining a high degree of solution accuracy. This hybrid perspective combines the strengths of exact optimization procedures with the computational advantages of heuristic methods.

In addition to theoretical developments, the chapter presents a comprehensive computational investigation of the proposed approach. Numerical experiments are conducted on representative many-to-one assignment instances involving multiple objectives related to cost, profit, and processing time. The performance of the proposed methodology is evaluated against several established approaches, including traditional weighted-sum methods, ε-constraint techniques, and evolutionary algorithms such as NSGA-II. Comparative analysis focuses on key performance indicators including solution quality, computational efficiency, convergence behavior, and the ability to approximate the true Pareto frontier.

A further contribution of this study is the incorporation of uncertainty considerations consistent with the interval-valued framework established in earlier chapters of the thesis. In practical applications, parameters such as costs, profits, processing times, and resource consumption levels are rarely known with complete certainty. Variations in market conditions, machine performance, labor productivity, and operational disruptions introduce uncertainty into the decision-making process. Therefore, the generalized assignment formulations developed in this chapter can accommodate interval-valued parameters, enabling the generation of solutions that remain effective under varying operational conditions.

Overall, this study represents a significant advancement of the assignment models studied previously by extending the analysis from constrained one-to-one assignments to more realistic many-to-one resource allocation environments. The proposed formulations and solution methodologies contribute toward addressing the research objectives related to generalized assignment structures, computational efficiency, and multi-objective optimization under uncertainty. Through mathematical modeling, heuristic lower-bound development, and extensive computational experimentation, the chapter provides a comprehensive framework for solving complex resource allocation problems encountered in modern operational systems.

Advanced Formulation: Many-to-One Assignment with Multiple Jobs per Resource

The importance of this advanced formulation within the present research lies in its ability to bridge the gap between theoretical optimization models and practical resource allocation systems. The multi-objective generalized assignment framework developed in this chapter extends the mathematical foundations established in previous chapters by introducing realistic operational considerations such as resource capacities, workload distributions, and multiple performance criteria. This extension directly addresses the limitations of conventional assignment models and enables the representation of a broader class of decision-making problems encountered in manufacturing systems, logistics networks, service operations, project management, and workforce scheduling.

Another significant aspect of the many-to-one assignment model is its compatibility with uncertainty modeling. As discussed in earlier chapters, operational parameters such as costs, profits, and processing times are often subject to fluctuations arising from market dynamics, machine performance variations, labor productivity differences, and environmental factors. The generalized assignment framework allows these parameters to be represented through interval values or other uncertainty measures, thereby enhancing the realism of the model. The integration of interval-based information into the assignment process enables decision-makers to obtain solutions that remain effective under a range of possible conditions rather than relying solely on deterministic estimates.

Mathematically, the generalized assignment problem can be viewed as a constrained optimization framework in which binary decision variables determine whether a particular job is assigned to a specific resource. The objective functions aggregate the effects of individual assignments in terms of cost, profit, and processing time, while the capacity constraints ensure the feasibility of resource utilization. The presence of multiple objectives transforms the problem into a multi-objective optimization model, where the concept of optimality is replaced by Pareto efficiency. A solution is considered efficient if no objective can be improved without causing deterioration in at least one of the remaining objectives. Consequently, the goal of the optimization process is not merely to identify a single best solution but rather to generate a set of non-dominated alternatives that support informed managerial decision-making.

The development of an advanced many-to-one assignment formulation is therefore essential for achieving the broader objectives of this research. It provides a realistic mathematical representation of complex allocation environments, accommodates multiple conflicting objectives, incorporates uncertainty considerations, and establishes the foundation for the algorithmic developments presented in subsequent sections. Furthermore, the formulation serves as the basis for evaluating the effectiveness of heuristic lower-bound strategies and alternative optimization approaches designed to improve computational efficiency and solution quality. By extending the scope of assignment theory beyond traditional one-to-one relationships, this chapter contributes toward the development of robust and practically relevant optimization methodologies capable of addressing the challenges of modern resource allocation systems.

Mathematical Model

The generalized multi-objective assignment problem considered in this research extends the classical assignment framework by allowing multiple jobs to be assigned to a single resource while respecting resource capacity limitations. Such a formulation is particularly suitable for practical environments where machines, workers, service facilities, transportation units, or computational resources are capable of processing multiple tasks within a given planning horizon.

Let the following notation be defined:

Let:

$I = 1, 2,…, m$ be the set of resources (machines, agents, facilities, etc.).
$J = 1, 2,…, n$ be the set of jobs/tasks to be assigned.

The binary decision variable is defined as:

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

Associated parameters for each feasible pair

i, j



c_{ij}

: Cost incurred when job

j

is assigned to resource

i



p_{ij}

: Profit generated when job

j

is assigned to resource

i



t_{ij}

: Processing time required for resource

i

to complete job

j



a_{ij}

: Amount of resource capacity consumed by assigning job

j

to resource

i



b_{i}

: Maximum available capacity of resource

i

The objective of the model is to simultaneously minimize cost, maximize profit, and minimize processing time while ensuring that all jobs are allocated feasibly.

Objective 1: Minimization of Total Cost

One of the primary concerns of any organization is reducing operational expenditure. The total assignment cost is obtained by summing the costs associated with all selected assignments.

Z_{1} = i = 1 m j = 1 n c_{ij} x_{ij}

\min Z_{1}

This objective attempts to allocate jobs to resources in a manner that minimizes overall expenditure.

For illustration, consider three jobs assigned as follows:

Assignment	Cost
Job 1 → Resource 1	20
Job 2 → Resource 2	35
Job 3 → Resource 1	25

Then

Z_{1} =20+35+25=80

Thus, the total assignment cost equals 80 units.

Objective 2: Maximization of Total Profit

In many industrial and business applications, maximizing profit is equally important. Different resources may generate different levels of profitability depending on their efficiency, expertise, or productivity.

The total profit is given by

Z_{2} = i = 1 m j = 1 n p_{ij} x_{ij}

The second objective becomes

\max Z_{2}

Suppose the corresponding profits are

Assignment	Profit
Job 1 → Resource 1	50
Job 2 → Resource 2	70
Job 3 → Resource 1	40

Then

Z_{2} =50+70+40=160

Hence, the total profit generated by the assignment plan is 160 units.

Because cost minimization and profit maximization are inherently conflicting objectives, decision-makers generally seek Pareto-efficient solutions rather than a single optimum.

Objective 3: Minimization of Time

Time is another critical performance indicator in resource allocation systems. Two alternative formulations are considered.

(a) Makespan Minimization

The first formulation minimizes the maximum workload assigned to any resource.

Z_{3} = i = 1 m j = 1 n t_{ij} x_{ij}

The objective becomes

\min Z_{3}

This measure is commonly known as the makespan.

Suppose the workloads are

Resource	Resource 1	Resource 2	Resource 3	Resource 4
Total Assigned Time	8	6	10	7

Then

Z_{3} = \max 8,6,10,7

)=10

The optimization process attempts to reduce this maximum value to achieve balanced resource utilization.

(b) Total Processing Time Minimization

Alternatively, the total completion time can be minimized.

Z_{3} = i = 1 m j = 1 n t_{ij} x_{ij}

If the selected assignments require times = 4,3,5,2,6units respectively, then

Z_{3} =4+3+5+2+6=20

The objective becomes

\min Z_{3}

To linearize the makespan for mixed-integer programming solvers, introduce an auxiliary variable

M \geq T_{i}

for all

i

, and minimize

M

M \geq j = 1 n t_{ij} x_{ij}, \forall i \in I

\min M

This formulation is useful when the focus is on overall operational efficiency rather than workload balancing.

Assignment Constraints

Every job must be assigned to exactly one resource.

Mathematically,

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

This guarantees complete task allocation.

For example, if Job 5 can be assigned to Resources 1, 2, and 3,

x_{15} + x_{25} + x_{35} =1

Possible feasible assignment:

1+0+0=1
or

0+1+0=1
but
1+1+0=2

is infeasible because one job would be assigned twice.

Capacity Constraints

The defining characteristic of the generalized assignment problem is the existence of resource capacities.

Each resource possesses a finite amount of available capacity represented by

b_{i}

The capacity restriction is

j = 1 n a_{ij} x_{ij} \leq b_{i}, \forall i \in I

where

a_{ij}

denotes the amount of capacity consumed.

Suppose Resource 1 has capacity

b_{1} =10

and assigned jobs consume

a_{11} =3, a_{12} =4 a_{13} =2

Then

3+4+2=9
Since

9≤ 10

the assignment is feasible.

However,

3+4+5=12
would violate the capacity constraint because

12>10
making the solution infeasible.

Binary Restrictions

The assignment variables are binary.

x_{ij} \in 0, 1, \forall i \in I, \forall j \in J

This condition ensures that a job is either assigned or not assigned.

Fractional allocations such as

x_{ij} =0.5

are not permitted in the classical generalized assignment framework.

Multi-Objective Model

Combining all objectives and constraints, the complete formulation is

\min Z_{1} & = i = 1 m j = 1 n c_{ij} x_{ij} \max Z_{2} & = i = 1 m j = 1 n p_{ij} x_{ij} \min Z_{3} & = \max i \in I j = 1 n t_{ij} x_{ij} (or total time variant)

subject to

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

j = 1 n a_{ij} x_{ij} \leq b_{i}, \forall i \in I

x_{ij} \in 0, 1, \forall i \in I, j \in J .

T_{1} = 4 + 5 = 9, T_{2} = 3 ⟹ Z_{3} = \max 9, 3 = 9

Capacity check (assume

b_{1} = 10

b_{2} = 10

3 + 2 = 5 \leq 10

4 \leq 10

Incorporation of Interval Data

To accommodate uncertainty, the model allows parameters to be represented as interval numbers.

For costs,

c_{ij} = c ij L, c ij U

where

c ij L

denotes the minimum possible cost and

c ij U

denotes the maximum possible cost.

For example,

c_{23} = 15, 20

indicates that the actual cost may vary between 15 and 20 units.

Similarly,

p_{ij} = p ij L, p ij U

and

t_{ij} = t ij L, t ij U

represent interval-valued profits and processing times.

The interval-valued objective functions become

Z_{1} = i = 1 m j = 1 n c ij L x_{ij}, i = 1 m j = 1 n c ij U x_{ij}

Z_{2} = i = 1 m j = 1 n p ij L x_{ij}, i = 1 m j = 1 n p ij U x_{ij}

Z_{3} = i = 1 m j = 1 n t ij L x_{ij}, i = 1 m j = 1 n t ij U x_{ij} (total time)

To obtain computationally tractable solutions, interval arithmetic, midpoint ranking methods, signed-distance ranking techniques, or robust optimization procedures discussed in Chapter 3 may be employed.

Thus, the proposed formulation represents a generalized interval-valued multi-objective assignment model capable of handling multiple jobs per resource, capacity restrictions, conflicting objectives, and parameter uncertainty simultaneously. This mathematical framework serves as the foundation for the lower-bound strategies, algorithmic developments, and computational experiments presented in the subsequent sections of this chapter.

Heuristic Lower-Bound Exploration

The generalized multi-objective assignment problem formulated in the previous section belongs to the class of NP-hard combinatorial optimization problems. As the number of resources and jobs increases, the size of the feasible solution space grows exponentially, making the direct application of exact optimization methods computationally expensive. In multi-objective environments, the challenge becomes even greater because the objective is not merely to identify a single optimal solution but rather to generate a set of Pareto-optimal solutions representing different trade-offs among cost, profit, and time. Consequently, reducing computational effort while maintaining solution quality becomes an important research objective.

One effective strategy for improving computational efficiency is the use of lower-bound techniques. A lower bound represents an estimate of the best possible value that an objective function can attain under relaxed conditions. Such bounds provide valuable information regarding the structure of the solution space and guide the optimization process toward promising regions. In the context of multi-objective assignment problems, lower bounds are particularly useful for generating high-quality initial solutions, reducing the search domain, accelerating convergence, and improving the effectiveness of scalarization-based approaches such as the weighted-sum method and ε-constraint technique.

The fundamental idea behind heuristic lower-bound exploration is to construct approximate solutions that are computationally inexpensive to obtain while remaining sufficiently close to the optimal region of the Pareto frontier. These approximations serve as starting points for more sophisticated optimization procedures. Instead of exploring the entire feasible space blindly, the algorithm begins its search near regions that are likely to contain efficient solutions. This significantly reduces computational time and improves overall solution quality.

Mathematically, consider the multi-objective generalized assignment problem:

The multi-objective generalized assignment problem can be stated as:

\min Z_{1} x, \max Z_{2} x, \min Z_{3} x

subject to

x \in X,

where

X

denotes the feasible region defined by the assignment, capacity, and binary constraints given in previous section

For a minimization objective, a lower bound

LB

satisfies:

LB \leq Z k *

where

Z k *

is the optimal (or ideal) value of objective

k

. For a maximization objective, an upper bound

UB

satisfies:

UB \geq Z k * .

These bounds provide important reference values that help evaluate the quality of candidate solutions and guide the optimization procedure.

Lower Bound Strategies

1. Relaxed Single-Objective Bounds

The first lower-bound strategy is obtained by relaxing the integrality restrictions imposed on the assignment variables. Instead of requiring

The first strategy relaxes the integrality condition

x_{ij} \in 0, 1

to:

0 \leq x_{ij} \leq 1, \forall i \in I, j \in J .

This transforms the integer programming problem into a linear programming problem that can be solved efficiently using standard optimization techniques.

For the cost minimization objective, the relaxed problem becomes:

L B_{1} =min i = 1 m j = 1 n c_{ij} x_{ij}

subject to

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

0 \leq x_{ij} \leq 1, \forall i, j .

The optimal value of this linear program provides a valid lower bound:

L B_{1} \leq Z 1 *

For example, consider the cost matrix

C = 1012158141391116 .

The linear relaxation may yield

L B_{1} = 31.5

, while the integer optimal solution is

Z 1 * = 34

, satisfying

31.5 \leq 34

confirming the validity of the lower bound.

Similar relaxations can be solved independently for

Z_{2}

(yielding an upper bound

U B_{2}

) and

Z_{3}

(yielding a lower bound

L B_{3}

The Hungarian method can also be employed when assignment constraints dominate the structure of the problem. Solving individual objectives separately provides useful estimates of ideal objective values.

2. Greedy Lower Bounds

A computationally inexpensive alternative involves constructing solutions through greedy allocation principles.

For each assignment pair, an efficiency ratio is computed.

For profit-cost analysis,

R ij 1 = \frac{p_{ij}}{c_{ij}} (profit per unit cost),

For profit-time analysis,

R ij 2 = \frac{p_{ij}}{t_{ij}} (profit per unit time) .

Assignments are ranked in descending order of efficiency.

Suppose

Assignment	Profit	Cost	Ratio
(1,1)	60	20	3.00
(2,1)	45	18	2.50
(3,1)	30	15	2.00

The algorithm first selects assignment ((1,1)) because it yields the highest ratio.

The process continues until all jobs are assigned and capacity constraints are satisfied.

Assume four jobs generate

P= 60,50,45,40

with corresponding costs C=(20,25,18,16)

Then

Z_{2} =  60+50+45+40=195

Z_{1} =  20+25+18+16=79

This feasible solution becomes an initial estimate for subsequent optimization.

Although greedy solutions are not guaranteed to be optimal, they are typically located near high-quality regions of the feasible space and therefore serve as excellent initialization points.

Lagrangian Relaxation

Lagrangian Relaxation Lagrangian relaxation targets the capacity constraints. For multipliers $λ_{i} \geq 0$ , the Lagrangian function is:

L x, λ = i = 1 m j = 1 n c_{ij} x_{ij} + i = 1 m λ_{i} j = 1 n a_{ij} x_{ij} - b_{i} .

Simplifying:

L (x, λ)= i = 1 m j = 1 n (c_{ij} + λ_{i} a_{ij}) x_{ij} - i = 1 m λ_{i} b_{i} .

The Lagrangian dual problem is:

θ λ = \min x \in X^{'} L x, λ,

where

X^{'}

is the relaxed feasible set (usually ignoring capacity). The best lower bound is obtained by solving the dual:

L B_{L} = \max λ \geq 0 θ λ .

Numerical Illustration

Let

c_{11} = 10

a_{11} = 4

b_{1} = 8

, and

λ_{1} = 2

. Then the modified cost is:

c_{11} + λ_{1} a_{11} = 10 + 2 \times 4 = 18 .

Suppose after solving subproblems,

θ λ = 142

and the best feasible integer solution is

Z^{*} = 150

. The gap is:

\frac{150 - 142}{150} \times 100 = 5.33 %.

Initial Pareto Approximation

In multi-objective optimization, generating an initial approximation of the Pareto frontier is often beneficial.

A weighted-sum scalarization can be formulated as

\min w_{1} Z_{1} x - w_{2} Z_{2} x + w_{3} Z_{3} x

subject to

x \in X

, where

w_{1} + w_{2} + w_{3} = 1

and

w_{i} \geq 0

Different weight combinations generate different efficient solutions.

For example,

Different weight vectors (e.g.,

0.5, 0.3, 0.2

0.3, 0.5, 0.2

) produce different efficient points such as

250, 500, 12

and

280, 580, 14

Collecting multiple solutions provides an initial Pareto approximation.

These solutions act as search seeds for advanced methods such as NSGA-II, MOEA/D, or hybrid ε-constraint algorithms.

The initial Pareto set can be represented as

P_{0} = x^{1}, x^{2},…, x^{k},

where each

x^{r}

is a non-dominated solution.

denotes a non-dominated solution.

The optimization process subsequently refines this approximation until convergence criteria are satisfied.

Role of Lower Bounds in the Proposed Algorithm

The proposed algorithm employs all four lower-bound mechanisms sequentially. First, linear relaxations establish theoretical performance limits. Second, greedy heuristics rapidly generate feasible solutions. Third, Lagrangian relaxation strengthens the bounds by incorporating capacity information. Finally, weighted-sum approximations construct an initial Pareto frontier.

Let

 Linear relaxations (

L B_{R}

) → theoretical performance limits,

 Greedy heuristics (

L B_{G}

) → fast feasible solutions,

 Lagrangian relaxation (

L B_{L}

) → tightened bounds,

 Weighted-sum scalarization → initial Pareto set

P_{0}

The overall initialization framework is:

S_{0} = L B_{R}, L B_{G}, L B_{L}, P_{0} .

where (

s_{0}

) denotes the initial search state.

Rather than exploring the entire feasible region (X), the optimization process focuses on a reduced region

X^{'} ⊆X

containing high-quality candidate solutions.

Consequently, the computational complexity is significantly reduced while maintaining proximity to the true Pareto frontier. The use of heuristic lower-bound exploration therefore plays a critical role in improving convergence speed, enhancing solution quality, and supporting the efficient generation of non-dominated solutions for large-scale generalized assignment problems.

Numerical Case Studies

To demonstrate the practical applicability of the proposed multi-objective generalized assignment framework, a numerical case study is presented involving a medium-sized resource allocation problem. The purpose of this case study is to illustrate the implementation of the mathematical model developed in Section 5.2 and the heuristic lower-bound exploration strategy discussed in Section 5.3. The example highlights how the proposed methodology generates efficient solutions while balancing conflicting objectives related to cost minimization, profit maximization, and completion time minimization under capacity constraints and interval uncertainty.

The problem consists of four machines (resources) and eight jobs (tasks). Each machine possesses a finite processing capacity representing the maximum workload that can be accommodated during the planning horizon. The capacity vector is defined as

b=(10,8,12,9)
where Machine 1 has a capacity of 10 units, Machine 2 has a capacity of 8 units, Machine 3 has a capacity of 12 units, and Machine 4 has a capacity of 9 units.

The set of machines is

I= M_{1}, M_{2}, M_{3}, M_{4}

and the set of jobs is

J= J_{1}, J_{2}, J_{3}, J_{4}, J_{5}, J_{6}, J_{7}, J_{8} .

To incorporate uncertainty, assignment costs, profits, and processing times are represented by interval values. The midpoint values are used during the initial optimization stage, while interval bounds are utilized during sensitivity analysis.

Cost Matrix

The midpoint cost matrix is assumed as

C= 253228 35      30     27     24     29 302631 33     28     29     25      27 223026 29     27     24     23     28 272925 31     26      28     22     24

P= 657268 80     75    70     60     74 706672 76     71    69     65     68 627570 78    73     67    64      72 687069 79    74     71     63      66

where each element

c_{ij}

represents the cost associated with assigning job (j) to machine (i).

Profit Matrix

The profit matrix is given by

P= 657268 80     75    70     60     74 706672 76     71    69     65     68 627570 78    73     67    64      72 687069 79    74     71     63      66

where

p_{ij}

denotes the expected profit generated by a particular assignment.

Processing Time Matrix

The processing times are represented by

T== 342 5     4     3     2     3 433 4     3     4     2      3 243 4     3     2     3     4 332 4     3      3     2     2

and the corresponding resource consumptions are assumed to coincide with the processing times.

Initial Lower-Bound Computation

Following the methodology proposed in Section 5.3, the optimization procedure begins with lower-bound generation.

Step 1: Greedy Initialization

For each assignment pair, a profit-to-cost efficiency ratio is computed:

R_{ij} = \frac{p_{ij}}{c_{ij}}

For example,

R_{11} = 65 / 25 =2.60

R_{31} = 62 / 22 =2.82

R_{47} = 63 / 22 =2.86

Assignments with higher efficiency ratios are prioritized while respecting machine capacities.

After the greedy allocation process, the following feasible assignment schedule is obtained:

Job	J1	J2	J3	J4	J5	J6	J7	J8
Assigned Machine	M3	M2	M4	M1	M3	M3	M4	M1

The resulting objective values are

Z_{1} =258

Z_{2} =503

Z_{3} =8.2

These values provide an initial approximation of the efficient region.

Step 2: Lagrangian Relaxation

The capacity constraints

n

j=1 a_{ij} x_{ij} \leq b_{i} are relaxed using multipliers

λ= 1.2,1.5,1.0,1.3

The modified objective becomes

L x,λ = i = 1 m j = 1 n c_{ij} + λ_{i} a_{ij} x_{ij} - i=1 m λ_{i} b_{i}

After solving the resulting subproblems, the Lagrangian lower bound is obtained as

LB=236.8

while the best feasible solution identified at this stage has

Z_{1} =248

yielding a gap of

\frac{248-236.8}{248} ×100= 4.52%

which indicates that the lower-bound estimate is relatively strong

Pareto Solution Generation

Once suitable lower bounds have been established, scalarization methods are employed to generate efficient solutions.

Weighted-Sum Approach

The scalarized objective is defined as

Z

w_{1} Z_{1} - w_{2} Z_{2} + w_{3} Z_{3}

subject to

w_{1} + w_{2} + w_{3} =1

Different weight combinations generate different trade-off solutions.

Solution A Cost-Oriented

Weights:

w_{1}, w_{2}, w_{3}

0.60,0.25,0.15

Resulting objectives:

Z_{1} =232

Z_{2} =475

Z_{3} =7.8

This solution minimizes cost but sacrifices profit.

olution B Balanced

Weights:

w_{1}, w_{2}, w_{3}

0.40,0.40,0.20

Resulting objectives:

Z_{1} =245

Z_{2} =520

Z_{3} =7.5

This solution represents a balanced compromise among all three objectives and

emerges as a non-dominated solution.

Solution C Profit-Oriented

Weights:

w_{1}, w_{2}, w_{3}

0.20,0.60,0.20

Resulting objectives:

Z_{1} =268

Z_{2} =556

Z_{3} =8.3

Although profit increases significantly, both cost and makespan increase.

Example Non-Dominated Assignment

One representative Pareto-optimal solution is shown below.

Job	J1	J2	J3	J4	J5	J6	J7	J8
Machine	M3	M2	M4	M1	M1	M3	M4	M2

The corresponding machine workloads are

Machine	M1	M2	M3	M4
Workload	7	6	7.5	5

The makespan is therefore

Z_{3} =max 7,6,7.5,5 =7.5

The total cost becomes

Z_{1} =245

and the total profit becomes

Z_{2} =520

Hence,

Z_{1}, Z_{2}, Z_{3}

245,520,7.5

which constitutes a non-dominated solution since no other feasible solution simultaneously decreases cost and makespan while increasing profit.

Pareto Frontier Interpretation

The generated Pareto frontier demonstrates the conflicting nature of the objectives.

Solution	Cost	Profit	Makespan
A	232	475	7.8
B	245	520	7.5
C	268	556	8.3

The results indicate that increasing profitability generally requires assigning jobs to more productive but expensive machines, thereby increasing overall cost. Similarly, reducing makespan often necessitates additional workload redistribution, which may increase both cost and operational complexity.

Sensitivity Analysis

To evaluate the robustness of the proposed model, machine capacities are varied by ±10% and ±15%.

Case 1: Capacity Increase (+10%)

New capacities:

b= 11,8.8,13.2,9.9

The optimization procedure yields

Z_{1} =243

Z_{2} =532

Z_{3} =7.2

Profit improves while completion time decreases due to greater scheduling flexibility.

Case 2: Capacity Reduction -10%

New capacities:

b= 9,7.2,10.8,8.1

Results:

Z_{1} =255

Z_{2} =506

Z_{3} =8.0

The reduced feasible region causes cost increases and profit reductions.

Case 3: Capacity Reduction -15%

New capacities:

b= 8.5,6.8,10.2,7.7

Results:

Z_{1} =262

Z_{2} =495

Z_{3} =8.6

Although performance deteriorates, feasible solutions continue to exist, indicating the robustness of the proposed framework.

CONCLUSION

Therefore, The numerical investigation demonstrates that the proposed lower-bound-assisted optimization approach effectively identifies high-quality Pareto-optimal solutions for the generalized assignment problem. The integration of greedy initialization, Lagrangian relaxation, and scalarization techniques substantially reduces the search effort while maintaining solution quality. The balanced non-dominated solution ((245,520,7.5)) provides an attractive compromise among operational cost, profitability, and completion time. Furthermore, the sensitivity analysis confirms that the model remains stable under moderate variations in resource capacities, with objective values changing gradually rather than abruptly. These findings validate the effectiveness of the proposed methodology and establish its suitability for solving realistic many-to-one assignment problems under multi-objective and uncertain environments.

References:

Alkayal, E. (2018). Optimizing resource allocation using multi-objective particle swarm optimization in cloud computing systems (Doctoral dissertation, University of Southampton). ePrints Soton.
Anvari, S., & Turkay, M. (2017). The facility location problem from the perspective of triple bottom line accounting of sustainability. International Journal of Production Research, 55(21), 6266–6287. [https://doi.org/10.1080/00207543.2017.1341632](https://doi.org/10.1080/00207543.2017.1341632)
Cattrysse, D. G., & Van Wassenhove, L. N. (1992). A survey of algorithms for the generalized assignment problem. European Journal of Operational Research, 60(3), 260–272. [https://doi.org/10.1016/0377-2217(92)90077-M](https://doi.org/10.1016/0377-2217(92)90077-M)
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197. [https://doi.org/10.1109/4235.996017](https://doi.org/10.1109/4235.996017)
Díaz, J. A., & Fernández, E. (2002). A tabu search heuristic for the generalized assignment problem with multiple objectives. Journal of Heuristics, 8(4), 407–430. [https://doi.org/10.1023/A:1015481708899](https://doi.org/10.1023/A:1015481708899)
Florios, K., & Mavrotas, G. (2014). Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems. Applied Mathematics and Computation, 237, 1–19. [https://doi.org/10.1016/j.amc.2014.03.110](https://doi.org/10.1016/j.amc.2014.03.110)
Holzmann, T., & Smith, J. C. (2018). Solving discrete multi-objective optimization problems using modified augmented weighted Tchebychev scalarizations. European Journal of Operational Research, 271(2), 436–449. [https://doi.org/10.1016/j.ejor.2018.05.041](https://doi.org/10.1016/j.ejor.2018.05.041)
Jaszkiewicz, A. (2018). Many-objective Pareto local search. European Journal of Operational Research, 271(3), 1001–1013. [https://doi.org/10.1016/j.ejor.2018.05.060](https://doi.org/10.1016/j.ejor.2018.05.060)
Konur, D., Farhangi, H., & Dagli, C. H. (2016). A multi-objective military system of systems architecting problem with inflexible and flexible systems: formulation and solution methods. OR Spectrum, 38(4), 967–1006. [https://doi.org/10.1007/s00291-016-0437-0](https://doi.org/10.1007/s00291-016-0437-0)
Lourenço, L. L., Armentano, V. A., & Laguna, M. (2001). A multi-objective heuristic for the generalized assignment problem. Journal of the Operational Research Society, 52(11), 1243–1253. [https://doi.org/10.1057/palgrave.jors.2601217](https://doi.org/10.1057/palgrave.jors.2601217)
Mavrotas, G. (2009). Effective implementation of the $\epsilon$-constraint method in multi-objective mathematical programming problems. Applied Mathematics and Computation, 213(2), 455–465. [https://doi.org/10.1016/j.amc.2009.03.037](https://doi.org/10.1016/j.amc.2009.03.037)
Ngo, T. S., Jaafar, J., Aziz, I. A., Aftab, M. U., Nguyen, H. Giang, & Bui, N. A. (2022). Metaheuristic algorithms based on compromise programming for the multi-objective urban shipment problem. Entropy, 24(3), 388. [https://doi.org/10.3390/e24030388](https://doi.org/10.3390/e24030388)
Ngulo, U. (2021). Decomposition methods for combinatorial optimization (Doctoral dissertation, Linköping University). DiVA Portal.
Öztürk, D. T., & Köksalan, M. (2016). An interactive approach for biobjective integer programs under quasiconvex preference functions. Annals of Operations Research, 244(2), 677–696. [https://doi.org/10.1007/s10479-015-2092-2](https://doi.org/10.1007/s10479-015-2092-2)
Ross, G. T., & Soland, R. M. (1975). A branch and bound algorithm for the generalized assignment problem. Mathematical Programming, 8(1), 91–103. [https://doi.org/10.1007/BF01580430](https://doi.org/10.1007/BF01580430)
Shresthamali, S., Kondo, M., & Nakamura, H. (2022). Multi-objective resource scheduling for IoT systems using reinforcement learning. Journal of Low Power Electronics and Applications, 12(4), 53. [https://doi.org/10.3390/jlpea12040053](https://doi.org/10.3390/jlpea12040053)
Tariri, G. (2013). The assignment problem with dependent costs (Doctoral dissertation, University of Louisville). ThinkIR.
Wang, Y. (2025). Research on multi-objective emergency resource scheduling optimization in chemical industrial parks. PMC Operational Systems, Article PMC12483207.
Weerasena, L., Ebiefung, A., & Skjellum, A. (2022). Design of a heuristic algorithm for the generalized multi-objective set covering problem. Computational Optimization and Applications, 82(3), 717–751. [https://doi.org/10.1007/s10589-022-00366-4](https://doi.org/10.1007/s10589-022-00366-4)
Wu, L., Zhao, T., & Cai, X. (2026). Interval multi-objective multi-task production scheduling method for manufacturing uncertainty. International Journal of Software Engineering and Knowledge Engineering, 36(12), 2650018X. [https://doi.org/10.1142/S021819402650018X](https://doi.org/10.1142/S021819402650018X)
Yagmahan, B., & Yenisey, M. M. (2010). A multi-objective ant colony system algorithm for flow shop scheduling problems. Expert Systems with Applications, 37(2), 1361–1368. [https://doi.org/10.1016/j.eswa.2009.06.104](https://doi.org/10.1016/j.eswa.2009.06.104)
Zhang, W., Bao, X., Hao, X., & Gen, M. (2025). Metaheuristics for multi-objective scheduling problems in industry 4.0 and 5.0: a state-of-the-arts survey. Frontiers in Industrial Engineering, 3, Article 1540022. [https://doi.org/10.3389/fieng.2025.1540022](https://doi.org/10.3389/fieng.2025.1540022)