A Branch And Bound Algorithm For Sub-contractor Selection In Agile Manufacturing Environment

ARTICLE IN PRESS

Int. J. Production Economics 87 (2004) 195–205

A branch and bound algorithm for sub-contractor selection in agile manufacturing environment W.H. Ipa, K.L. Yunga, Dingwei Wangb,* b

a Department of Manufacturing Engineering, The Hong Kong Polytechnic University, Hung Hom, Hong Kong Institute of Systems Engineering, Northeastern University, Box 135, Shenyang 110004, People’s Republic of China

Received 20 February 2001; accepted 25 April 2003

Abstract Partnership and partner selection play a key role for ‘‘Opportunity Driven’’ project contractors in agile manufacturing environment. In this paper, we present an investigation on the partner selection problems with engineering projects. Firstly, the problem is described by a 0–1 integer programming with non-analytical objective function. It is proven that the partner selection problem is a type of earliness and tardiness production planning problems. By introducing the concepts of inefficient and ideal candidates, we propose the theory of solution space reduction which can efficiently reduce the complexity of the problem. Then, a branch and bound algorithm embedded project scheduling is developed to obtain the solution. The approach was demonstrated by the use of an experimental example drawn from a construction project of coal fire power station. The computational results have been found to be satisfactory. r 2003 Elsevier Science B.V. All rights reserved. Keywords: Branch and bound; Project management; Partner selection; Virtual enterprise; Integer programming; Agile manufacturing; Earliness/tardiness scheduling

1. Introduction To win the competition in the global manufacturing environment the cooperation and collaboration among enterprises play a key role in the current years (Hellard, 1995). This global partnership can be seen in the philosophy of agile manufacturing where the operation and production of a manufacturing enterprise will be driven by opportunity, the tender calling for projects in *Corresponding author. Tel.: +2483682292; fax: +2483683138. E-mail address: [email protected] (Dingwei Wang).

internet (Goldman et al., 1995). Once an enterprise wins a bid, it usually has to call tenders for partial sub-projects of the bid won. Although there are many factors to effect partner selection such as friendship, quality, serve, flexibility, credit and reliability, the key trade-off is based upon the cost and completion time. On the other hand, other factors are not easy to be quantified in the mathematical models except the cost and completion time. Very often the bid prices offered by various candidates for the same sub-project may be very different. The larger company used to ask for a higher price with a shorter processing time, but the smaller one for a lower price and longer

0925-5273/03/$ - see front matter r 2003 Elsevier Science B.V. All rights reserved. doi:10.1016/S0925-5273(03)00125-7

ARTICLE IN PRESS 196

W.H. Ip et al. / Int. J. Production Economics 87 (2004) 195–205

time. In addition, there is also a tardiness penalty cost if the contracted project cannot be completed before its due date. Thus, an effective approach to select the optimal combination of partners will be necessary for the optimization of resource allocation in an agile manufacturing environment. Partnership and partner selection have been attracting many researchers on agile manufacturing and supply chain management (Gunasekaran, 1998; Maloni and Benton, 1997). The partner selection is also an important function for information management systems of extended/ virtual enterprises (Davis and O’Sullivan, 1999; Korhonen et al., 1998). However, the mathematical models and optimization methods for partner selection are still a challenge to operations research (Gunasekaran, 1998; Maloni and Benton, 1997). Talluri and Baker (1999) proposed a two-phase mathematical programming approach for the partner selection in designing a virtual enterprise. In view of the fact that the sub-projects contracted by partners consist of an activity network with precedence (Elmaghraby, 1977). Each partner works in the project as a ring in the chain. Thus, the problem is considered as a partner selection problem embedded project scheduling (Brucker et al., 1999). Since the investment for the project is usually paid to the main contractor by installments. The investment can be described as a cash flow that often cannot meet the requirement from the sub-project contractors. Thus, the main contractor has to loan from banks and pay interest to bank. Owing to the complexity of sub-contractor selection problem, it is not easy to be solved by general mathematical programming methods. Branch and bound method is a powerful tool to solve this kind of combinatorial optimizations (Taha, 1975). The different varieties of branch and bound are widely applied into various problems in production planning and scheduling and found to be generally satisfactory (Crauwels et al., 1998; Perregaad and Clousen, 1998; Wang et al., 1998). In this study, we describe the sub-contractor selection problem by a 0–1 integer programming with non-analytical objective function. It can be proved that the problem is a type of earliness and tardiness planning problems (Baker and Scudder, 1990; Wang, 1995). By defining the inefficient

candidate and ideal candidate, the theorems on the solution space reduction are proposed. Then, a branch and bound algorithm with project scheduling is developed to obtain the partner selection solution. The approach was applied to an experimental example drawn from an actual construction project of coal-fire power station. The results show us that the suggested approach can achieve optimal solution efficiently for most middle size problems. The rest of the paper is organized as follows. A formal description of the problem and models are given in Section 2. Then, the theory on the solution space reduction is discussed in Section 3. The suggested branch and bound algorithm embedded project scheduling is presented in Section 4. The experimental example and computational results are included in Section 5. Finally, the concluding remarks and further works are given in Section 6.

2. Problem and model of sub-contractor selection For readers’ convenience, a list of notations is given here. n D b a r f ðtÞ F ði; kÞ H mi bij pij cn xij x ZðxÞ

number of jobs included in project due-date of project penalty cost for tardiness of a period rate of first payment to sub-contractors interest rate of loan from bank cash flow paid to the main contractor by the project owner in period t total investment for the project from owner connected job pair set of all connected job pairs number of candidates bidding for job i bid cost of candidate j for job i bid completion time of candidate j for job i completion time of final job, i.e. the completion time of the project 0–1 assignment variable. xij ¼ 1 means the job i is contracted to j matrix variable for all xij : It is a completed selection objective value achieved by selection x

ARTICLE IN PRESS W.H. Ip et al. / Int. J. Production Economics 87 (2004) 195–205

si ci Ok IðOk Þ

beginning time of job i in selection x completion time of job i in selection x index of job sequenced at kth place with the kth larger mean cost assigned candidate index of job Ok (the job at the k-place in the sequence)

The sub-contractor selection problem can be described as follows: Assuming a global enterprise (main contractor) wins a bid of a big project consisted of some sub projects. To describe the sub projects easily and clearly, we call them jobs. The enterprise is not able to complete the whole project by its own capacity and resources. Therefore, it has to call tender for these jobs. The project is consisted of n jobs. Because the precedence relationship between these jobs, they form an activity network (Elmaghraby, 1977). If job k can only begin after the completion of job i; i.e. job i precedes job k; we note the connected job pair by ði; kÞAH: There H is the set of all connected job pairs. For the convenience of description, we label these jobs such that iok; 8ði; kÞAH: Without the loss of generality, the final job is labeled as job n: If final job cannot be determined, a virtual final job can be created. Its completion time cn is defined as the completion time of the project. The project owner will pay the main contractor the construction cost by a cash flow noted as f ðtÞX0; t ¼ 1; 2; y; D; where D is the due date of the project. If the project is tardy, the main contractor will receive a tardiness penalty of b for per tardy period. For job i; i ¼ 1; 2; y; n; there are mi qualified candidates responded to the tender invitation. The qualification for candidates means their credit and quality can meet the requirement of the project. For the candidate j of job i; its bid cost is bij and processing time is pij periods. To simplify the problem, we assume that the main contractor will pay the job cost to the selected sub-contractors by installments. The first payment is a  bij ð0oao1Þ at the beginning of the job i and the remained ð1  aÞ  bij at the completion time of the job i; i ¼ 1; 2; y; n: Since the cash flow may not meet the requirement of sub-projects, the money shortage would

197

happen. In the case of money shortage, the main contractor may loan from a bank with an interest rate of r > 0: The objective is to select the optimal combination of sub-contractors for all jobs to minimize the total cost of the project including the job costs to all selected partners, the loan interest to bank and the tardiness penalty to the project owner. Defining the variables 8 1; job i is contracted to > > > < candidate j and 8i; j; t: ð1Þ xij ðtÞ ¼ > begins at period t; > > : 0; otherwise; Then, the problem can be described by the following model: mi cn n X X X min ZðxÞ ¼ bij xij ðtÞ x

i¼1

þ r

j¼1 cn X

t¼1

" a

mi X n t X X

t¼1

j¼1

i¼1

mi X n t X X

þ ð1  aÞ

i¼1



t X

j¼1

#þ f ðtÞ

bij xij ðtÞ

t¼1

bij xij ðt  pij Þ

t¼1

þb½cn  D þ

ð2Þ

t¼1 mi X cn X

s:t:

j¼1 mi X cn X j¼1

i ¼ 1; 2; y; n;

ð3Þ

ðt þ pij Þxij ðtÞ

t¼1

p

mk X cn X j¼1

mn X cn X j¼1

xij ðtÞ ¼ 1;

t¼1

txkj ðtÞ; 8ði; kÞAH;

ð4Þ

t¼1

ðt þ pnj Þxnj ðtÞ ¼ cn ;

ð5Þ

t¼1

xij ðtÞ ¼ 1 or 0; þ

8i; j; t;

ð6Þ

where ½v stands for maxf0; vg: Since the objective function is not continuous and differentiable, the model cannot be solved by general mathematical programming approaches.

ARTICLE IN PRESS W.H. Ip et al. / Int. J. Production Economics 87 (2004) 195–205

198

Thus, we attempt to use branch and bound method to obtain the solution (Taha, 1975). Although there is no earliness penalty in the objective function (2), it is a type of earliness and tardiness planning problems as long as the tardiness penalty cost b is large enough (Baker and Scudder, 1990; Wang, 1995). It can be seen that the earlier beginning of any job can cause a higher interest cost from possible loan. While the project may be delayed as late as possible if the tardiness penalty is cheaper than the loan interest. In this case, we can only obtain a meanless singular solution. Therefore, the first problem we consider is when the solution is not singular. Definition 1. Problem (2)–(6) is regular if its objective function is of earliness and tardiness. Let the total investment of the project, F ; be F¼

D X

f ðtÞ:

ð7Þ

t¼1

Theorem 1 in the following gives a sufficient condition for regular solution. Theorem 1. Problem (2)–(6) is regular if bXrF : The proof of Theorem 1 is given in the appendix. Theorem 1 is explicit in practice, for the investor, the profit per period of the project must be greater than the interest of total investment at least. And, the tardiness penalty must be greater than the lost profit of project for per period at least. Therefore, the sufficient condition for regular solution mentioned in Theorem 1 can be easily obtained in practice.

The size of the solution space (the number of feasible solutions) of problem (2)–(6), N; is n Y i¼1

mi :

Definition 2. The candidate j of job i is inefficient if there exists a candidate k for the same job with bik pbij ; pik opij or bik obij ; pik ppij : Theorem 2. If problem (2)–(6) is regular, there exists at least one optimal solution not including any inefficient candidates. The proof of Theorem 2 is given in the appendix. According to Theorem 2 we can ignore all inefficient candidates in the procedure to solve problem (2)–(6) without the loss of optimal solution. Thus, the solution space can be reduced efficiently. Since the procedure of project scheduling can only be done after each job has been assigned to a candidate, the branch and bound algorithm for the partner selection problem will be difficult to eliminate any branches. To come over the difficulty, we introduce the concept of ideal candidate. Definition 3. The ideal candidate of a job i is a virtual candidate labeled by 0 with bi0 ¼ minfbij ; j ¼ 1; 2; y; mi g and pi0 ¼ minfpij ; j ¼ 1; 2; y; mi g: It means the ideal candidate of a job is better than any real candidates of the job in both of cost and processing time. Thus, we have the following Theorem 3. Theorem 3. If the problem is regular, the objective value of a real solution is greater than or equal to the objective value achieved by partly replacing its candidates by the relative ideal candidates.

3. Inefficient and ideal candidates

N¼

It is evident that the size is very large even for a small scale problem. For example, N ¼ 520 ¼ 9:5367  1013 for a problem with 20 jobs and 5 candidates for each job. Therefore, the reduction of solution space is very important.

ð8Þ

The proof of Theorem 3 is given in the appendix. Theorem 3 is the basic theory for the proposed branch and bound algorithm, it tells us that we can eliminate the branches with the objective values

ARTICLE IN PRESS W.H. Ip et al. / Int. J. Production Economics 87 (2004) 195–205

over bound by partly replacing candidates by relative ideal candidates.

Calculate the objective value by " #þ cn X n t t X X X bi þ r RðtÞ  f ðtÞ ZðxÞ ¼ i¼1

4. Branch and bound algorithm embedded project scheduling The basic idea of the proposed branch and bound algorithm embedded project scheduling is to select the optimal partner combination by branch and bound at the first level of algorithm, and to schedule all jobs with a fixed partner combination at the second level. Once the candidates for all jobs are fixed, the project scheduling can be done by the following Procedure PS. To minimize the loan interest, the basic idea is to schedule all jobs as late as possible subject to the precedence constrains. To simplify the description, we assume the candidates j1 ; j2 ; y; jn are selected for job i; i ¼ 1; 2; y; n; respectively. Then we define bi ¼ biji ; pi ¼ piji ;

i ¼ 1; 2; y; n:

ð9Þ

Procedure PS: Step 1: From job i ¼ 1 to n; calculate the initial starting time si and the completion time ci by 8 > < maxfck ; 8ðk; iÞAHg if there exists ðk; iÞAH; if there does not exist si ¼ 1 > : ðk; iÞAH; and ci ¼ si þ pi : Step 2: Fix the project completion time of job n by cn and the starting time of job n by sn : From i ¼ n to 1, adjust the initial starting time si and the completion time ci by ci ¼ minfsk ; 8ði; kÞAHg

and

s i ¼ c i  pi :

Step 3: Calculate the money requirement, RðtÞ; from period t ¼ 1 to cn by X X RðtÞ ¼ abi þ ð1  aÞbi : si ¼t

ci ¼t

Step 4: Set xiji ðsi Þ ¼ 1; 8i; and all other xij ðtÞ ¼ 0:

199

t¼1

t¼1

t¼1

þ b½cn  D þ and return to the main routing of branch and bound. To improve the branch cutting procedure, we sequence the jobs on the descending order of the means of job costs. We use the notation O1 ; O2 ; y; On to represent the sequence of mean costs, i.e. Ok ¼ i means the cost of job i is kth larger in all jobs. The computation experiences show us that it can efficiently decrease the computation time. The basic idea on branch cutting is to check the combination of the first k jobs assigned to real candidates and the remained n  k jobs assigned to ideal candidates. If the objective value is greater than the bound, by the theorem 3 the branch can be eliminated. Otherwise, we assign a real candidate to the ðk þ 1Þth job, and check the objective value again. We use IðOk Þ ¼ j to represent the job Ok is assigned to its jth candidate. When the computation is at level k; for the assignment IðO1 Þ; IðO2 Þ; y; IðOk Þ; IðOkþ1 Þ; y; IðOn Þ; we have IðOi Þ > 0 for ipk; and IðOi Þ ¼ 0 for i > k: It means the first k jobs are assigned to real candidates and the rest final n  k jobs to ideal candidates, i.e. 0: Once the objective value achieved by the assignment, ZðIÞ; is greater than the bound, the computation for this branch will be eliminated. The step by step procedure of the branch and bound algorithm embedded project scheduling is described as follows: Procedure BB: Step 1: Calculate the means of bid costs of all jobs by mi 1 X % ¼ CðiÞ cij ; i ¼ 1; 2; y; n: mi j¼1 Step 2: Sequence jobs on the descending order of % CðiÞ; i.e. the sequencing job series is O1 ; O2 ; y; On such that % 2 ÞX?XCðO % n Þ: % 1 ÞXCðO CðO

ARTICLE IN PRESS W.H. Ip et al. / Int. J. Production Economics 87 (2004) 195–205

200

Step 3: Set Bound ¼ BP and the search level index k ¼ 1; where BP is a big positive number. Step 4: Assign job Ok to its 1st candidates and jobs Okþ1 ; y; On to their ideal candidates, i.e. let candidate index IðOk Þ ¼ 1 and IðOj Þ ¼ 0; 8j > k: Step 5: Call the Procedure PS to calculate the objective value of current combination, ZðxÞ: Step 6: If ZðxÞXBound; go to Step 8. Otherwise go to next step. Step 7: If kon; set k’k þ 1 and go to Step 4. Otherwise update Bound ¼ ZðxÞ and xn ¼ x: Step 8: Assign next candidate to job k; i.e. set IðOk Þ’IðOk Þ þ 1 and IðOj Þ ¼ 0; 8j > k: Step 9: If IðOk ÞpmOk ; go to Step 5. Otherwise set k’k  1 Step 10: If k ¼ 0; go to Step 11. Otherwise go to Step 8. Step 11: Output Zðxn Þ ¼ Bound and xn as optimal solution.

Table 1 The job list and evaluated costs and processing times No.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Job name

Cost (106 RMB)

Processing time (Mon.)

Total design of system Design of railway for coal Construction of railway Design of boiler system Manufacturing of boilers Design of buildings Construction of buildings Design of generators Design of electric transmission Manufacturing of generators Assembling of boilers Manufacturing of transmission equipment Desg.& asmb. of computer control system Assembling of generators Assembling of transmission system System inspection and test running

15 2 25 10 120 10 40 10 10

6 4 10 6 12 6 10 6 6

90

12

5 45

3 12

45

16

10 10

3 3

20

5

Note that Step 1 is to calculate the means of bid costs for all jobs. Step 2 is to sequence the jobs by the means from large to small in order to improve the computation efficiently. Step 3 sets the initial

Fig. 1. The Example of the node pair scheme.

Table 2 The numbers of qualified candidate for jobs Job Candidate num.

1 4

2 6

3 5

4 2

5 2

6 7

7 4

8 8

9 3

10 4

11 5

12 3

13 6

14 3

15 4

16 2

ARTICLE IN PRESS W.H. Ip et al. / Int. J. Production Economics 87 (2004) 195–205 Table 3 (continued)

Table 3 The list of candidates for all jobs Job no.

1

2

3

4

Candidate code

Job no.

Cost (millions of RMB)

Candidate code

Cost (millions Processing of RMB) time (months)

J3 J4

80.0 105.0

13 8

11

K1 K2 K3 K4 K5

6.0 5.0 7.0 4.0 5.5

3 3 2 4 3

12

L1 L2 L3

40.0 38.0 48.0

12 14 10

M1 M2 M3 M4 M5 M6

30.0 38.0 50.0 55.0 60.0 48.0

18 17 12 10 8 15

N1 N2 N3

8.0 12.0 10.0

4 2 3

P1 P2 P3 P4

12.0 10.0 8.0 6.0

2 3 3 5

Q1 Q2

16.0 20.0

6 5

Processing time (months)

A1 A2 A3 A4

18.0 16.0 14.5 12.0

4 5 5 6

B1 B2 B3 B4 B5 B6

1.9 2.0 2.5 1.8 1.5 2.2

4 3 3 5 6 3

C1 C2 C3 C4 C5

20.0 22.5 25.0 27.0 18.5

12 11 10 8 13

D1 D2

10.0 12.0

6 4

13

14 5

6

7

8

9

10

201

E1 E2

120.0 130.0

12 10

F1 F2 F3 F4 F5 F6 F7

12.0 14.0 10.0 14.5 8.0 9.0 7.0

4 4 5 3 7 6 8

15

G1 G2 G3 G4

12.0 14.0 10.0 8.0

5 4 7 8

H1 H2 H3 H4 H5 H6 H7 H8

35.0 30.0 38.0 40.0 48.0 45.0 42.0 43.0

12 13 11 10 8 8 10 10

I1 I2 I3

11.0 8.0 12.0

5 7 4

J1 J2

98.0 88.0

10 12

bound and the search index. Steps 4 to 10 are the backbone of the branch and bound algorithm. Step 4 assigns the job at kth level to 1st candidate and the jobs at lower levels to their ideal candidates. Step 5 calls the subroutine of project scheduling to calculate the objective value of current partner combination. Step 6 checks the current bound. If current bound is over, go to Step 8 for changing a branch. Step 7 checks if all orders are included, update the bound and solution, otherwise goes to Step 4 down to the next level. Step 8 is used to cut current branch and move to next one. Step 9 checks if the search for all branches in this level is finished, then goes up a level to the next branch. Step 10 checks if the search returns to the top level, the search procedure terminates and goes to Step 11 to output results.

16

ARTICLE IN PRESS W.H. Ip et al. / Int. J. Production Economics 87 (2004) 195–205

202

5. Numerical analysis The algorithm was coded by FORTRAN and run at a Pentium II/366 machine, satisfactory results were achieved. The example of the problem is a real life problem of the construction project of a coal-fire power station. The project consists of 16 jobs with their evaluated cost and processing times as shown in Table 1, its due date is 36 months. The tardiness penalty is RMB 48 millions for one month. The payment rule for all jobs is 55% at the beginning and the rest when the job is completed. The loan interesting rate is 0.6% per month. The precedence relationship represented by the Activity-on Arc mode is shown in Fig. 1. After the main contractor won the project. It call tenders for the sixteen jobs. The numbers of the qualified candidates for all jobs are shown in Table 2. Their bidding cost and required processing time are listed in Table 3. The total investment is RMB 485 millions. We can see, the problem is regular due to 0:006  485o48: The cash flow is shown in the second column of Table 5. The size of the solution space is 2:787  109 : By Theorem 2, nine inefficient candidates (A2, B3, F3,

H5, H7, H8, K1, K5 and P2) are identified and removed. The size is reduced considerably to 3:359  108 : The optimal solution is shown in Table 4, its total cost is RMB 472.4842 millions, and the completion time is 36 and is just in time. The main contractor can obtain a profit of RMB 12.52 millions from the project. The cash flow, payment flow and the money surplus or shortage are shown in Table 5. To test the performance of the recommended branch and bound algorithm embedded project scheduling (BB/PS), we randomly produced some problems with different sizes. The results together with the comparison of the algorithm with the branch and bound algorithm without sequencing the cost means on descent (BB-NoSeq.) is shown in Table 6. In the table, ‘‘PS Times’’ stands for the times to call Procedure PS (project scheduling) and ‘‘CPU Time’’ for the computation time by CPU; ‘‘—’’ means cannot get solution in acceptable time. From Table 6, we see that the problem size grows with the job number very fast. The solution reduction technique and resequencing the jobs on the bid cost have significantly improved the computation.

Table 4 The sub-contractors of optimal solution Job no.

Sub-contractor

Cost

Proc. time

Begg. time

Compl. time

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

A1 B2 C5 D2 E1 F7 G2 H6 I3 J3 K3 L1 M3 N2 P1 Q2

18.00 2.00 18.50 12.00 120.00 7.00 14.00 45.00 12.00 80.00 7.00 40.00 50.00 12.00 12.00 20.00

4 3 13 4 12 8 4 8 4 13 2 12 12 2 2 5

1 1 4 5 13 9 9 17 13 14 25 17 19 27 29 31

5 4 17 9 25 17 13 25 17 27 27 29 31 29 31 36

ARTICLE IN PRESS W.H. Ip et al. / Int. J. Production Economics 87 (2004) 195–205

203

Table 5 The cash flow, requirement and surplus/shortage Period t

Cash flow

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

Payment flow

Remainder/shortage

At t

Until t

At t

Until t

þ=

30.00 0.00 0.00 30.00 0.00 0.00 30.00 0.00 0.00 30.00 0.00 0.00 40.00 0.00 0.00 40.00 0.00 0.00 40.00 0.00 0.00 40.00 0.00 0.00 50.00 0.00 0.00 50.00 0.00 0.00 50.00 0.00 0.00 55.00 0.00 0.00

30.00 30.00 30.00 60.00 60.00 60.00 90.00 90.00 90.00 120.00 120.00 120.00 160.00 160.00 160.00 200.00 200.00 200.00 240.00 240.00 240.00 280.00 280.00 280.00 330.00 330.00 330.00 380.00 380.00 380.00 430.00 430.00 430.00 485.00 485.00 485.00

11.00 0.00 0.00 11.07 14.70 0.00 0.00 0.00 16.95 0.00 0.00 0.00 78.90 44.00 0.00 0.00 63.63 0.00 27.50 0.00 0.00 0.00 0.00 0.00 78.10 0.00 45.75 0.00 30.00 0.00 38.90 0.00 0.00 0.00 0.00 9.00

11.00 11.00 11.00 22.08 36.78 36.78 36.78 36.78 53.73 53.73 53.73 53.73 132.63 176.72 176.83 176.83 240.69 240.94 268.61 268.78 268.95 268.95 268.95 268.95 347.15 347.26 393.39 393.47 423.73 423.73 463.09 463.28 463.48 463.48 463.48 472.48

19.00 19.00 19.00 37.92 23.22 23.22 53.22 53.22 36.27 66.27 66.27 66.27 27.38 16.72 16.83 23.17 40.69 40.94 28.61 28.78 28.95 11.05 11.05 11.05 17.15 17.26 63.39 13.47 43.73 43.99 33.09 33.28 33.48 21.52 21.52 12.52

Table 6 The results for the problems with different sizes n

16 22 27 30 38 48

Size

2:787  109 4:741  1013 5:461  1016 3:277  1018 3:963  1023 2:466  1029

Reduced size

3:359  108 1:088  1012 9:404  1014 2:257  1016 3:510  1020 4:912  1025

Algorithm BB/PS

Algorithm BB-NoSeq.

PS times

CPU time

PS times

CPU time

20, 267 290, 661 248, 013 445, 260 5, 512, 132 401, 272, 400

1.3200 15.7100 14.6100 30.8700 458.4700 42457.7300

172, 136 3400824 — — — —

6.1000 1801.2800 — — — —

ARTICLE IN PRESS 204

W.H. Ip et al. / Int. J. Production Economics 87 (2004) 195–205

6. Concluding remarks

as

The work on the sub-contractor selection problem of extended enterprises show us that the mathematical model (2)–(6) provide a formal description for the sub-contractor selection problems. It has the potential to be an efficient quantitative tool for more complex partnership analysis in the virtual global business environment. Besides the concepts and theorems on the inefficient and ideal candidates provides the foundation of the branch and bound to reduce the solution space. Thus, the recommended branch and bound algorithm embedded project scheduling can achieve the optimal solution of the mentioned problems of middle size. It can be applied into practical partner selection and sub-project management problems. The criteria used to select partners in a real life perspective usually include quality, serve, credit and more other factors beside cost and completion time. How to quantify these factors for mathematical models is the further investigation. On the other hand, due to the limitation of branch and bound method, the proposed algorithm cannot solve large scale problems in an acceptable time. To overcome the computation limitation by using soft computing approaches for the partner selection problems is another further work (Zadeh, 1994; Wang et al., 1999).

ZðxÞ ¼

Acknowledgements The authors wished to acknowledge the support of the Hong Kong Polytechnic University research grant (G-YB95), and also the National Natural Science Foundation (No.60084003, 70171056) and the Education Ministry Key Lab Foundation of Shantou University of P.R. China.

mi n X X i¼1

þ r

Proof of Theorem 1. To simplify the description, let a ¼ 1: The objective function ZðxÞ is rewritten

j¼1

xij ðtÞ

t¼1

" cn mi X n t X X X t¼1

j¼1

i¼1

bij xij ðtÞ 

t¼1

t X

#þ f ðtÞ

t¼1

þ b½cn  D þ :

ðA:1Þ

Assuming xðtÞ; t ¼ 1; 2; y; cn ; is a solution of (2)– (6), then, xðt % þ 1Þ ¼ xðtÞ; t ¼ 1; 2; y; cn ; is also a solution with one period of delay to xðtÞ: It is clear, xðtÞ % can meet all constrains (3)–(6) and c%n ¼ cn þ 1: The difference of two objective values is ZðxÞ  ZðxÞ % " #þ cn X mi X n t t X X X ¼r bij xij ðtÞ  f ðtÞ t¼1

r

i¼1

j¼1

t¼1

" c%n X mi X n t X X i¼1

t¼1

j¼1

t¼1

bij x% ij ðtÞ 

t¼1

t X

#þ f ðtÞ

t¼1

þ b½cn  D þ  b½c%n  D þ " #þ cn X mi X n t t X X X ¼r bij xij ðtÞ  f ðtÞ t¼1

r

i¼1

j¼1

t¼1

t¼1

" cX mi X n t n þ1 X X t¼1

i¼1



j¼1

t X

bij xij ðt  1Þ

t¼1

#þ

f ðtÞ

t¼1

þ b½cn  D þ  b½cn  D þ 1 þ " #þ cn X mi X n t t X X X ¼r bij xij ðtÞ  f ðtÞ t¼1

r

i¼1

j¼1

t¼1

" cX mi X n t1 n þ1 X X t¼1

i¼1

j¼1

t¼1

bij xij ðtÞ 

t¼0

t X

#þ f ðtÞ

t¼1

þ b½cn  D þ  b½cn  D þ 1 þ " #þ cn X mi X n t t X X X ¼r bij xij ðtÞ  f ðtÞ t¼1

Appendix A

cn X

bij

r

i¼1

j¼1

t¼1

" cn X mi X n t X X t¼1

i¼1

j¼1

t¼1

bij xij ðtÞ 

t¼1

þ b½cn  D þ  b½cn  D þ 1 þ :

tþ1 X t¼1

#þ f ðtÞ

ARTICLE IN PRESS W.H. Ip et al. / Int. J. Production Economics 87 (2004) 195–205

Note: We remove the second ½ þ when t ¼ 0; because it is equal to zero by xij ð0Þ ¼ 0; 8i; j; and f ð1ÞX0: Define yðtÞ ¼

mi X n t X X i¼1

j¼1

t¼1

bij xij ðtÞ 

tþ1 X

f ðtÞ;

t¼1

then, ZðxÞ  ZðxÞ % ¼r

cn X

f½yðtÞ þ f ðt þ 1Þ þ  ½yðtÞ þ g

t¼1

þ b½cn  D þ  b½cn  D þ 1 þ : Case 1: cn oD: We have b½cn  D þ ¼ b½cn  D þ 1 þ ¼ 0; then, ZðxÞ  ZðxÞX0; % because ½yðtÞ þ f ðt þ 1Þ þ X½yðtÞ þ 8t: Case 2: cn XD: ZðxÞ  ZðxÞ % cn X f½yðtÞ þ f ðt þ 1Þ þ  ½yðtÞ þ g  b ¼r t¼1

pr

cn X

f ðt þ 1Þ  bprF  bp0:

t¼1

Proof of Theorem 2. Assume x0 ðtÞ; t ¼ 1; 2; y; cn ; is an optimal solution with an inefficient candidate j for job i: By Definition 2, there is a candidate k of job i with bik pbij ; pik opij or bik obij ; pik ppij : Replace the candidate j of job i by k for solution x0 ðtÞ; t ¼ 1; 2; y; cn ; we get a new solution xðtÞ; t ¼ 1; 2; y; cn : It is easy to prove that ZðxÞpZðx0 Þ as long as problem (2)–(6) is regular. Therefore, xðtÞ; t ¼ 1; 2; y; cn ; is also an optimal solution, or the assumption is not true. Proof of Theorem 3. Assume xðtÞ; t ¼ 1; 2; y; cn ; is a solution, and x0 ðtÞ; t ¼ 1; 2; y; c0n ; is a virtual solution same as xðtÞ; t ¼ 1; 2; y; cn ; except that the candidate j of job i is replaced by the ideal candidate 0 of job i: From Definition 3, we have bi0 pbij and pi0 ppij : Replace xðtÞ; t ¼ 1; 2; y; cn ; in the objective function (2) by x0 ðtÞ; t ¼ 1; 2; y; c0n ; clearly, c0n pcn : It is easy to prove that ZðxÞXZðx0 Þ as long as problem (2)–(6) is regular.

205

References Baker, K.R., Scudder, G.D., 1990. Sequencing with earliness and tardiness penalties: A review. Operations Research 38, 22–36. Brucker, P., Drexl, A., Mohring, R., Neumann, K., Pesch, E., 1999. Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research 112, 3–41. Crauwels, H.A.J., Hariri, A.M.A., Potts, C.N., Van Wassenhove, L.N., 1998. Branch and bound algorithms for single machine scheduling with batch set-up time to minimize total weighted completion time. Annals of Operations Research 83, 57–76. Davis, M., O’Sullivan, D., 1999. Systems design framework for the extended enterprise. Production Planning and Control 10, 3–18. Elmaghraby, S.E., 1977. Activity Networks—Project Planning and Control by Network Models. Wiley, New York. Goldman, S., Nagel, R., Preiss, K., 1995. Agile Competitors and Virtual Organizations. Van Nostrand Reinhold, New York. Gunasekaran, A., 1998. Agile manufacturing: Enablers and an implementation framework. International Journal of Production Research 36, 1223–1247. Hellard, R.B., 1995. Project Partnering Principle and Practice. Thomas Telford Publications, London. Korhonen, P., Huttunen, K., Eloranta, E., 1998. Demand chain management in global enterprise–information management view. Production Planning and Control 9, 526–531. Maloni, M.J., Benton, W.C., 1997. Supply chain partnerships: Opportunities for operations research. European Journal of Operational Research 101, 419–429. Perregaad, M., Clousen, J., 1998. Parallel branch and bound methods for the job-shop scheduling problem. Annals of Operations Research 83, 137–160. Taha, H.A., 1975. Integer Programming Theory, Applications, and Computations. Academic Press, New York. Talluri, S., Baker, R.C., 1999. A framework for designing efficient value chain networks. International Journal of Production Economics 62, 133–144. Wang, D., 1995. Earliness/tardiness production planning approaches for manufacturing systems. Computers & Industrial Engineering 28, 425–436. Wang, D., Fang, S.-C., Hodgson, T.J., 1998. A fuzzy due-date bargainer for make-to-order manufacturing systems. IEEE Transactions on SMC Part C: Application and Reviews 28, 492–497. Wang, D., Fang, S.-C., Nuttle, H.L.W., 1999. Soft computing for multi-customer due-date bargaining. IEEE Transactions on SMC Part C: Application and Reviews 29, 566–575. Zadeh, L.A., 1994. Fuzzy logic, neural networks and soft computing. Communications of the ACM 37, 77–84.