机械英文文献

本资料包含pdf文件1个，下载需要1积分

机械英文文献Scheduling operations on parallel machine tools
BRYAN A. NORMAN1;
and JAMES C. BEAN2
1
Department of Industrial Engineering， University of Pittsburgh， Pittsburgh， PA 15261， USA
E-mail: banorman###engrng.pitt.edu
2
Department of Industrial and Operations Engineering， University of Michigan， Ann Arbor， MI 48109， USA
E-mail: jbean###umich.edu
Accepted June 1998
We introduce unique scheduling problems that arise for multiple spindle machine tools. The ability of these machines to perform
simultaneous operations on more than one part creates constraints that are not found in the traditional scheduling literature. Two
types of solution procedures are introduced for these problems. The ®rst uses priority dispatching rules and a delay factor concept，
while the second uses a genetic algorithm with a random keys encoding. The e€ectiveness of these methods is demonstrated on test
problems with comparisons to lower bounds.
1. Introduction to parallel machine tools
Machining hardware advances drive changes in require-
ments for Computer-Aided Process Planning (CAPP)
systems. To gain the full bene®t of improvements in
hardware， CAPP software that can exploit these im-
provements must be developed. A key di€erence between
Parallel Machine Tools (PMTs) and conventional CNC
machines is that the former contain multiple spindles and
can hold multiple workpieces concurrently. As a result， a
PMT can process more than one workpiece at a time and/
or perform more than one operation at a time. This vi-
olates the most basic assumptions of traditional sched-
uling or process planning.
To properly describe PMTs it is necessary to de®ne
some terms. We retain the terminology introduced in
Levin and Dutta [1]. A Part Machining Location (PML)
refers to a valid workholding location. The main spindle
and subspindle(s) always represent valid PMLs. A Ma-
chining Unit (MU) refers to a tool holding device， which
may hold a single tool or a turret containing multiple
tools. Relative motions between the tool on the MU and
the workpiece held in the PML accomplish the machin-
ing. Conventional machines have only one MU and one
PML. PMTs have PMLmax… 1† PMLs and MUmax… 1†
MUs. PMLmax indicates the maximum number of work-
pieces on the machine at one time， and MUmax the max-
imum number of operations being carried out
simultaneously. Note that this is much more general than
traditional machines that， with lockstepped PMLs and
MUs， can make multiple identical copies of the same part
simultaneously. For a more detailed discussion of the
structure of PMTs， see Levin and Dutta [1].
Due to the presence of multiple PMLs and multiple
MUs， PMTs o€er new challenges for process planning
systems. Most of the existing process planning and
scheduling literature assumes that machines can process
only one part at a time and that only one operation can
be performed on a part at a time. However， PMTs are not
limited by these assumptions.
The scheduling of operations on a PMT has not re-
ceived much attention in the literature. Two papers that
discuss process planning for PMTs， Levin and Dutta [1]
and Yip-Hoi and Dutta [2]， mention the importance of
scheduling operations eciently but do not discuss how
to achieve this goal. Some of the technological constraints
of PMTs and their impact on the operation scheduling
problem are discussed in Levin et al. [3]. They propose a
procedure based on the idea of Gi‚er and Thompson [4]
for constructing feasible semi-active schedules. Yip-Hoi
and Dutta [5] present a genetic algorithm for sequencing
operations.
The traditional production scheduling literature fails to
address the problems that arise for PMTs due to the
common assumption of serial operations. However， some
simpli®ed versions of the PMT scheduling problem are
similar to problems that have been considered in the lit-
erature. These similarities will be noted in Section 2.
CAPP for PMTs opens many areas for research in-
cluding feature extraction， collision avoidance， user in-
terfaces and operation sequencing. In this paper we 
Corresponding author
0740-817X Ó 2000 ``IIE
IIE Transactions (2000) 32， 449±459