abstract

this paper explores the hierarchical production planning (hpp) problem of flexible automated workshops

(faws) each of which has a number of flexible manufacturing systems (fmss). the objective is to decompose

medium-term production plans (assigned to an faw by erp/mrp ii) into short-term production plans (to be

uted by fmss in the faw) so as to minimize cost on the condition that demands have just been met. herein

the hpp problem is formulated by a linear programming model with the overload penalty different from the

underload penalty and with demand constraints. since the scale of the model for a general workshop is too large to

be solved in the simplex method on a personal computer within acceptable time karmarkar’s algorithm and an

interaction/prediction algorithm respectively are used to solve the model the former for the large scale problems

and the latter for the very large scale. with the help of the above-mentioned algorithms and hpp examples

karmarkar’s algorithm and the interaction/prediction algorithm are compared and analyzed the results of which

show that the proposed approaches are quite effective and suitable for both ‘push’ and ‘pull’ production.

q 2004 elsevier ltd. all rights reserved.

keywords: flexible automated workshops; flexible manufacturing systems; hierarchical production planning; karmarkar’s

algorithm; interaction/prediction approach

1. introduction

the problem of production planning for a flexible automated workshop (faw) consisting of

flexible manufacturing systems (fmss or cells) is important and worth studying. in a manufacturing

ting production planning is essential to achieve efficient resource allocation over time in

meeting demands for finished products. since the scope of pp problems generally prohibits a

monolithic modeling approach a hierarchical production planning (hpp) approach has been widelyadvocated in the pp literature (davis & thompson 1993). to model pp problems the existing

hierarchical approaches usually employ the following concepts: (1) product disaggregation (bitran

haas & hax 1981; bitran & hax 1977; davis & thompson 1993; graves 1982; hax & meal

1975; newson 1975; saad 1988; simpson 1999; simpson & erenguc 1998; yeh tarng & chen

1988) (2) temporal decomposition (karmarkar 1988; malakooti 1989; nguyen & dupont 1993;

qiu & burch 1997; tsubone 1988) (3) process decomposition (villa 1989) and (4) eventfrequency decomposition (akella 1989; gershwin 1988; kimemia & gershwin 1983). however

those approaches are not quite suitable for the decomposition of medium-term production plans

(assigned to an faw by erp/mrp ii short for enterprise resource planning/manufacturing resource

planning) into short-term production plans (to be uted by fmss in the faw). to be specific

the product disaggregation only considers the structures of products instead of the organizational

structure of a manufacturing department. although the process decomposition considers the

organizational structure of the manufacturing department it only covers the manufacturing system

consisting of a forward chain of workshops. as the relationships among fmss in an faw are not

always serial or even very complicated the process decomposition is inapplicable to the

decomposition of medium-term production plans for faws. and the temporal and event-frequency

decomposition do not consider the organizational structure of the manufacturing department as

such either.

for this end yan (1997) and yan and jiang (1998) proposed two new approaches to the optimal

decomposition of production plans for faws with respect to delay interaction or not. by building up

linear quadratic models of pp problems and using interaction/prediction their proposed approaches

optimally decompose medium-term production plans (assigned to an faw by mrp ii/cims short for

computer integrated manufacturing system) into short-term production plans (to be uted by fmss in

the faw) at a high speed. these approaches combining the principles of both a temporal decomposition

and a process decomposition with the organizational structure of the faw are capable of solving verylarge-scale hpp problems. however their overload and underload penalty are the same. in practice the

wages for overtime are several times those for the usual hours and the underload only leads to the

decrease in the utilization of resources (such as men and equipment) so the overload penalty should be

much greater than the underload. besides only the manufacturers that can agilely respond to and

completely satisfy users’ demands can win a victory in the keen competition for markets while the

overproduction will lead to the increase in finished-product inventory and production cost. no doubt it is

desirable to just meet product demands without overproduction or underproduction. thus a linear

programming (lp) model with the overload penalty different from the underload penalty and with

demand constraints should be built up for decomposing medium-term production plans (assigned to an

faw by erp/mrp ii) into short-term production plans (to be uted by fmss in the faw). because

the model for a general workshop is of thousands upon thousands of constraints and variables it is

difficult to be solved by the simplex method on a personal computer within acceptable time. for this end

we propose that karmarkar’s algorithm and an interaction/prediction approach based on karmarkar’s

algorithm respectively should be applied to solving the model the former for the large scale problems

and the latter for the very large scale. the above-mentioned lp problem is also an hpp problem because

the karmarkar’s algorithm and interaction/prediction approach based on karmarkar’s algorithm for

solving it are in fact the methods to combine the principles of both a temporal decomposition and a

process one in hpp with the organizational structure of the faw.