T.C.

ISTANBUL AYDIN UNIVERSITY

FACULTY OF ENGINEERING
DEPARTMENT OF INDUSTRIAL ENGINEERING

MODELING IN INDUSTRIAL ENGINEERING

FIND OPTIMAL SOLUTION
DR. INSTRUCTOR MEMBER OF NIMA MIRZAEI

HOMEWORK REPORT

BESTE GÜLER – B1805.030041

GÖKÇE GÜRZ - B1805.030034
İLAYDA GÜRER – B1805.030037

1
ACKNOWLEDGEMENTS
We would like to thank Dr. Instructor Member of Nima Mirzaei for teaching us and helping
us.

2
LIST OF TABLES

Table1….………………………………………………………………………..…………….5
Table2 …………………………………………………………………………………….......6
Table3…………………………………………………………………………………………8

3
TABLE OF CONCENTS
1. PROBLEM ………………………………………………………………………5
2. FORMULATE THE PROBLEM…………………………………………..…..6
2.1 Definition Variables…………………………...................................………6
2.2 Creating Linear Constraints……………………………….....……7-8-9-10
2.3 Conclusion………………………………………..……………………..…10
3. FIND OPTIMAL SOLUTION………………………..…………11-12-13-14-15

4
1. PROBLEM

The Springfield School Board has made the decision to close one of its middle schools (sixth,
seventh, and eighth grades) at the end of this school year and reassign all of next year’s
middle school students to the three remaining middle schools. The school district provides
busing for all middle school students who must travel more than approximately a mile, so the
school board wants a plan for reassigning the students that will minimize the total busing cost.
The annual cost per student for busing from each of the six residential areas of the city to each
of the schools is shown in the following table (along with other basic data for next year),
where 0 indicates that busing is not needed and a dash indicates an infeasible assignment.

Are Number of Students Percentage Percentage Percentage Busing Cost per Student
a
in 6th Grade in 7th Grade in 8th Grade School School School 3
1 2

1 450 32 38 30 $300 $0 $700

2 600 37 28 35 — 400 500

3 550 30 32 38 600 300 200

4 350 28 40 32 200 500 —

5 500 39 34 27 0 — 400

6 450 34 28 38 500 300 0

School capacity: 900 1,100 1,000

Table(1)
The school board also has imposed the restriction that each grade must constitute between 30
and 36 percent of each school’s population. The above table shows the percentage of each
area’s middle school population for next year that falls into each of the three grades. The
school attendance zone boundaries can be drawn so as to split any given area among more
than one school, but assume that the percentages shown in the table will continue to hold for
any partial assignment of an area to a school.
You have been hired as a management science consultant to assist the school board in
determining how many students in each area should be assigned to each school.

5
2. FORMULATE THE PROBLEM
The board wants to build these numbers (distribution of students on different schools)
according to the following goals one at a time:
 Goal 1: Just the basic constraints that have been specified previously.
 Goal 2: In addition to the basic constraints, all the students form one area should go to the
same school. In other words, area’s 1 students (450 students) must go to either school 1, 2
or 3.
 Goal 3: Eliminate the bussing services for students living 1 to 1.5 miles away from their
schools. That means remove any cost that is equal to $200.
 Goal 4: Eliminate the bussing services for students living 1 to 2 miles away from their
schools. That means removing any cost that is equal to $200 and $300.

After assigning the students to the schools, the Springfield board members should further
analyze the different result for the “optimal” bussing cost against other measures. These
measures include safety and analyzing methods differences and efficiencies.
The situation described in the introduction can be redefined as a linear programming problem.
To do this we have to assign variables and create linear equations with logical operators to
replace the constraints.

2.1 Definition Variables

The next table will show the distribution of students from each area on the three different
schools (e.g. students form area 1 are divided to X1, X2, and X3 in school 1, 2 and 3
respectively.)

Number of Student in
Area School 1 School 2 School 3
1 X1 X2 X3
2 X4 X5 X6
3 X7 X8 X9
4 X10 X11 X12
5 X13 X14 X15
6 X16 X17 X18
Table (2)

6
2.2 Creating Linear Constraints
Constraint 1: The students in each area should be divided completely among the three
different schools. The following constrains will satisfy this condition:

X1 + X2+ X3 = 450
X4+ X5 + X6 = 600
X7+ X8+ X9 = 550
X10+ X11+ X12 = 350
X13+ X14+ X15 = 500
X16+ X17+ X18 = 450

Note: variable information from Table (2), number of student in each area from Table(1).
(e.g. X1 + X2+ X3 represent the total number of student assigned to the three different
schools and this total should equal to 450)

Constraint 2: The total number of students assigned to each school should not exceed the
limits presented in the Springfield information.

X1+ X4+ X7+ X10+ X13+ X16 <= 900

X2+ X5+ X8+ X11+ X14+ X17 <= 1,100
X3+ X6+ X9+ X12+ X15+ X18 <= 1,000

Note: variable information from Table [2], school capacity numbers from Table[1].(e.g. X1+
X4+ X7+ X10+ X13+ X16 <= 900 this means that the total number of students assigned to
school 1 from the six areas is less then or equal to the maximum capacity, which is 900
students.)

Constraint 3: The percentages of areas (area 1 though 6) that reside in each grade (6th,
7th, and 8th) are provided in Table (1). When we multiply the percentages of the 6th graders
in each area by the number of students from that area in the three schools we will have the
total number of 6th graders in that specific school.

7
 6th graders… Total number of 6th graders in each school (6S1, 6S2, and 6S3)
In school 1 0.32X1+0.37 X4+ 0.30X7+ 0.28X10+ 0.39X13+ 0.34X16 = 6S1
In school 2 0.32X2+ 0.37X5+ 0.30X8+ 0.28X11+ 0.39X14+ 0.34X17 = 6S2
In school 3 0.32X3+ 0.37X6+ 0.30X9+ 0.28X12+ 0.39X15+ 0.34X18= 6S3
7th graders… Total number of 6th graders in each school (6S1, 6S2, and 6S3)
In school 1 0.38X1+0.28 X4+ 0.32X7+ 0.40X10+ 0.34X13+ 0.28X16 = 7S1
In school 2 0.38X2+ 0.28X5+ 0.32X8+ 0.40X11+ 0.34X14+ 0.28X17 = 7S2
In school 3 0.38X3+ 0.28X6+ 0.32X9+ 0.40X12+ 0.34X15+ 0.28X18= 7S3
8th graders… Total number of 6th graders in each school (6S1, 6S2, and 6S3)
In school 1 0.30X1+0.35X4+ 0.38X7+ 0.32X10+ 0.27X13+ 0.38X16 = 8S1
In school 2 0.30X2+ 0.35X5+ 0.38X8+ 0.32X11+ 0.27X14+ 0.38X17 = 8S2
In school 3 0.30X3+ 0.35X6+ 0.38X9+ 0.32X12+ 0.27X15+ 0.38X18= 8S3
Table (3)
Note: the percentages are taken form Table (1) and variables taken from Table (2)

The previous numbers (total number of students in each grade for each school) should be with
in the range of 30% to 36% of the total number of students in each school. This will produce
the following constraints:

30% total number of student in school I <= 6th graders

and
36% total number of student in school I >= 6th graders
0.30(X1+ X4+ X7+ X10+ X13+ X16) <= 6S1 <= 0.36(X1+ X4+ X7+ X10+ X13+ X16)
0.30(X2+ X5+ X8+ X11+ X14+ X17) <= 6S2 <= 0.36(X2+ X5+ X8+ X11+ X14+ X17)
0.30(X3+ X6+ X9+ X12+ X15+ X18) <= 6S3 <= 0.36(X3+ X6+ X9+ X12+ X15+ X18)

30% total number of student in school I <= 7th graders

and
36% total number of student in school I >= 7th graders
0.30(X1+ X4+ X7+ X10+ X13+ X16) <= 7S1 <= 0.36(X1+ X4+ X7+ X10+ X13+ X16)
0.30(X2+ X5+ X8+ X11+ X14+ X17) <= 7S2 <= 0.36(X2+ X5+ X8+ X11+ X14+ X17)
0.30(X3+ X6+ X9+ X12+ X15+ X18) <= 7S3 <= 0.36(X3+ X6+ X9+ X12+ X15+ X18)

30% total number of student in school I <= 8th graders

and
36% total number of student in school I >= 8th graders
0.30(X1+ X4+ X7+ X10+ X13+ X16) <= 8S1 <= 0.36(X1+ X4+ X7+ X10+ X13+ X16)
0.30(X2+ X5+ X8+ X11+ X14+ X17) <= 8S2 <= 0.36(X2+ X5+ X8+ X11+ X14+ X17)
0.30(X3+ X6+ X9+ X12+ X15+ X18) <= 8S3 <= 0.36(X3+ X6+ X9+ X12+ X15+ X18)

8
Analyzing Goal Programming 1:

The first goal is implemented using the previous basic variables and constraints. The values of
Table (1) and equations of the constraints are plugged into the solver in Microsoft Excel
solver and the result is presented in page [11].
We can see from the result how we will divide the student form each area among the three
schools. Also, we can see that the total cost of this allocation is $555,555.56. The allocation
and the bussing expense is the most optimal result can be obtained under the basic constraints.

Analyzing Goal Programming 2:

There are two approaches for analyzing:

Linear programming method:

In order to implement this method we have to add another group of constraints. These new
constraints make sure that all students form one area are assigned to the same school.

Mod(X1, 450) = 0 Mod(X2, 450) = 0 Mod(X3, 450) = 0

Mod(X4, 600) = 0 Mod(X5, 600) = 0 Mod(X6, 600) = 0
Mod(X7, 550) = 0 Mod(X8, 550) = 0 Mod(X9, 550) = 0
Mod(X10, 350) = 0 Mod(X11, 350) = 0 Mod(X12, 350) = 0
Mod(X13, 500) = 0 Mod(X14, 500) = 0 Mod(X15, 500) = 0
Mod(X16, 450) = 0 Mod(X17, 450) = 0 Mod(X18, 450) = 0

Note: Mod(X, N) is a function that output the remainder from dividing X by N. using this
function and making it equal to zero will assure that X is either 0 or N.

The previous constraints will assure that each school is assigned 0 or the maximum number of
students from each area. The result of this method gives a bussing cost of $420,000.00. The
results are presented in page [12].

Binary Linear programming methods:

In order to implement this method we have to add another group of constraints to the basic
groups. This new constraints make sure that all students from one area are assigned to the
same school.

X1 = 450* b1 X2=450* b2 X3=450* b3

X4 = 600* b4 X5= 600* b5 X6= 600* b6
X7= 550* b7 X8= 550* b8 X9= 550* b9
X10=350* b10 X11=350* b11 X12=350* b12
X13=500* b13 X14=500* b14 X15=500* b15
X16=450* b16 X17=450* b17 X18=450* b18
b1+ b2+ b3=1 b4+ b5+ b6=1 b7+ b8+ b9=1
b10+ b11+ b12=1 b13+ b14+ b15=1 b16+ b17+ b18=1

And {bi = binary where i=(1,2,3,4,…,18)}

The binary constraint will choose the value of each Xi i=(1,2,…,18) to be 0 or the maximum
student population in this area. The results for each binary number are not accurate but

9
rounded. The result is $420,000.00, which is equivalent to the previous method and the excel
sheet that present the results is on page [13].
Analyzing Goal Programming 3:

To delete the bussing cost for students that are 1 to 1.5 miles away from their schools, the
following constraints should be added to the basic groups: X9 = 0 , X10 = 0 (forcing the costs
of X9 and X10 to zero)
These constraints will eliminate the cost of $200 from the Table (1), which corresponds to
walking distance of 1 to 1.5 miles. The result for this optimization is displayed in page [14]
and the optimal bussing cost for this goal is $393,636.36.

Analyzing Goal Programming 4:

To delete the bussing cost for students that are 1 to 2 miles away from their schools, the
following constraints should be added: X1 = 0 , X8 = 0 , X9 = 0 , X10 = 0 , X17 = 0 (force
X1,8,9,10,17 to be zero)
These constraints will eliminate the cost of $200 and $300 from the Table (1), which
corresponds to walking distance of 1 to 2 miles. The result for this optimization is displayed
in page [15] and the optimal bussing cost for this goal is $340,053.76.

2.3 Conclusion
The final recommendation for the Springfield is that:
1. Based on the cheapest with the best safety satisfaction, goal 1 will be the best choice.
2. Based on increasing savings with sacrifice in safety limits (Students walking more
then 1 mile is 900 students), goal 3 will be the choice with savings of $161919.20
(saving of $179.90 per student).
3. Based on increasing savings with sacrifice in safety limits (Students walling more then
1 mile is 1313 students), goal 4 will be the choice with savings of $215501.80 (saving
of $164.13 per student).

So, final recommendation is to perform goal 3.

10
3. FIND OPTIMAL SOLUTION
Excel Solver

Goal 1: Basic Constraints

# of % in 6th % in 7th % in 8th Bussing Cost ($/student)
Area Students Grade Grade Grade School 1 School 2 School 3
1 450 0,32 0,38 0,30 300 0 700
2 600 0,37 0,28 0,35 N/A 400 500
3 550 0,30 0,32 0,38 600 300 200
4 350 0,28 0,40 0,32 200 500 N/A
5 500 0,39 0,34 0,27 0 N/A 400
6 450 0,34 0,28 0,38 500 300 0
Best Assignment:
# of Students Assigned Total # of
Area School 1 School 2 School 3 Total Students
1 0,00 450,00 0,00 450 = 450
2 0,00 422,22 177,78 600 = 600
3 0,00 227,78 322,22 550 = 550
4 350,00 0,00 0,00 350 = 350
5 366,67 0,00 133,33 500 = 500
6 83,33 0,00 366,67 450 = 450
Total 800 1100 1000

School Capacity 900 1100 1000

# of Students by Grade
School 1 School 2 School 3
6th Graders 269,33 368,56 339,11
7th Graders 288,00 362,11 300,89
8th Graders 242,67 369,33 360,00
30% of Total 240 330 300
36% of Total 288 396 360

Total Bussing Cost: $555.555,56

11
Goal 2: Linear Programming Method

# of % in 6th % in 7th % in 8th Bussing Cost ($/student)

Area Students Grade Grade Grade School 1 School 2 School 3
1 450 0,32 0,38 0,30 300 0 700
2 600 0,37 0,28 0,35 N/A 400 500
3 550 0,30 0,32 0,38 600 300 200
4 350 0,28 0,40 0,32 200 500 N/A
5 500 0,39 0,34 0,27 0 N/A 400
6 450 0,34 0,28 0,38 500 300 0

Best Assignment:
# of Students Assigned Total # of
Area School 1 School 2 School 3 Total Students
1 0 450 0 450 = 450
2 0 600 0 600 = 600
3 0 0 550 550 = 550
4 350 0 0 350 = 350
5 500 0 0 500 = 500
6 0 0 450 450 = 450
Total 850 1050 1000

School Capacity 900 1100 1000

# of Students by Grade
School 1 School 2 School 3
6th Graders 293,00 366,00 318,00
7th Graders 310,00 339,00 302,00
8th Graders 247,00 345,00 380,00
30% of Total 246,5 304,5 290
36% of Total 323 399 380

Mode function to keep students in one school

0 0 0 equal 0
0 0 0 equal 0
0 0 0 equal 0
0 0 0 equal 0
0 0 0 equal 0
0 0 0 equal 0

Total Bussing Cost: $420.000,00

12
Goal 2: Using Binary Linear Programming Method

# of % in 6th % in 7th % in 8th Bussing Cost ($/student)

Area Students Grade Grade Grade School 1 School 2 School 3
1 450 0,32 0,38 0,30 300 0 700
2 600 0,37 0,28 0,35 N/A 400 500
3 550 0,30 0,32 0,38 600 300 200
4 350 0,28 0,40 0,32 200 500 N/A
5 500 0,39 0,34 0,27 0 N/A 400
6 450 0,34 0,28 0,38 500 300 0

Best Assignment:
# of Students Assigned Total # of
Area School 1 School 2 School 3 Total Students
1 0,00 450,00 0,00 450 = 450
2 0,00 600,00 0,00 600 = 600
3 0,00 0,00 550,00 550 = 550
4 350,00 0,00 0,00 350 = 350
5 500,00 0,00 0,00 500 = 500
6 0,00 0,00 450,00 450 = 450
Total 850 1050 1000

School Capacity 900 1100 1000

# of Students by Grade
School 1 School 2 School 3
6th Graders 293,00 366,00 318,00
7th Graders 310,00 339,00 302,00 Total Bussing Cost: $420.000,00
8th Graders 247,00 345,00 380,00
30% of Total 246,5 304,5 290
36% of Total 323 399 380

Binary constraints sum

b1 b2 b3 | 0 1 0 1
b4 b5 b6 | 0 1 0 1
b7 b8 b9 | 0 0 1 1
b10 b11 b12 | 1 0 0 1
b13 b14 b15 | 1 0 0 1
b16 b17 b18 | 0 0 1 1

sum = 1
Xi*bi Xi*bi Xi*bi
$0,00 $450,00 $0,00
$0,00 $600,00 $0,00
$0,00 $0,00 $550,00
$350,00 $0,00 $0,00
$500,00 $0,00 $0,00
$0,00 $0,00 $450,00
i=(1,4,7,10,13,16)
i=(2,5,8,11,14,17)
i=(3,6,9,12,15,18)

13
Goal 3: Eliminating Bussing Cost $200

# of % in 6th % in 7th % in 8th Bussing Cost ($/student)

Area Students Grade Grade Grade School 1 School 2 School 3
1 450 0,32 0,38 0,30 300 0 700
2 600 0,37 0,28 0,35 N/A 400 500
3 550 0,30 0,32 0,38 600 300 0
4 350 0,28 0,40 0,32 0 500 N/A
5 500 0,39 0,34 0,27 0 N/A 400
6 450 0,34 0,28 0,38 500 300 0

Best Assignment:
# of Students Assigned Total # of
Area School 1 School 2 School 3 Total Students
1 0 450 0 450 = 450
2 0 600 0 600 = 600
3 0 0 550 550 = 550
4 350 0 0 350 = 350
5 318 0 182 500 = 500
6 132 50 268 450 = 450
Total 800 1100 1000

School Capacity 900 1100 1000

# of Students by Grade
School 1 School 2 School 3
6th Graders 266,91 383,00 327,09
7th Graders 285,09 353,00 312,91
8th Graders 248,00 364,00 360,00
30% of Total 240 330 300
36% of Total 288 396 360

Total Bussing Cost: $393.636,36

14
Goal 4: Eliminate Costs $200 and $300

# of % in 6th % in 7th % in 8th Bussing Cost ($/student)

Area Students Grade Grade Grade School 1 School 2 School 3
1 450 0,32 0,38 0,30 0 0 700
2 600 0,37 0,28 0,35 N/A 400 500
3 550 0,30 0,32 0,38 600 0 0
4 350 0,28 0,40 0,32 0 500 N/A
5 500 0,39 0,34 0,27 0 N/A 400
6 450 0,34 0,28 0,38 500 0 0

Best Assignment:
# of Students Assigned Total # of
Area School 1 School 2 School 3 Total Students
1 39 411 0 450 = 450
2 0 237 363 600 = 600
3 0 78 472 550 = 550
4 350 0 0 350 = 350
5 435 0 65 500 = 500
6 76 374 0 450 = 450
Total 900 1100 900

School Capacity 900 1100 1000

# of Students by Grade
School 1 School 2 School 3
6th Graders 306,00 369,75 301,25
7th Graders 324,00 352,25 274,75
8th Graders 270,00 378,00 324,00
30% of Total 270 330 270
36% of Total 324 396 324

Total Bussing Cost: $340.053,76

15
16