ISSN:
1572-9338
Keywords:
Sequencing
;
Hamiltonian paths
;
local searches
;
makespan
;
precedences
;
release dates
;
deadlines
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract Given a digraphG=(V, A), a weight for each node inV and a weight for each arc inA, the Sequential Ordering Problem (SOP) consists of finding a Hamiltonian path, such that a release date and a deadline for each node and precedence relationships among nodes are satisfied and a linear function is minimized. In our case, the objective function is the maximum cumulated potential of the nodes (also, the so-called makespan). The SOP has a broad range of applications, mainly in production planning and manufacturing systems. Nodes represent jobs (to be processed on a single machine), arcs represent sequencing of the jobs, the nodes' weights are the processing time for the jobs, the arcs' weights are the setup times for two consecutive jobs, and the cumulated potential of a node is the completion time of a job. The goal is to produce a feasible scheduling of the jobs so that the makespan is minimized. We present an approximate algorithm for improving feasible solutions to the SOP. The algorithm is based on two local searchκ-opt procedures to reduce the makespan while satisfying the time window (i.e. release date and deadline) and precedence constraints, forκ=3 and 4. The complexity of the algorithm isO(bn 4), wheren denotes the number of nodes andb is the average number of precedences per node. Extensive computational experience and implementation aspects are reported for very large-scale instances up to 3000 nodes and 9000 precedences. Experience with real-life cases is also reported.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02024937
Permalink
