This thesis deals with issues arising in manufacturing, in particular relatedto production efficiency. Lot streaming refers to the process of splitting jobsto move production through several stages as quickly as possible, whereasbatch scheduling refers to the process of grouping jobs to improve the use ofresources and customer satisfaction.We use a network representation and critical path approach to analyse thelot streaming problem of finding optimal sublot sizes and a job sequence ina two-machine flow shop with transportation and setup times. We introducea model where the number of sublots for each job is not predetermined,presenting an algorithm to assign a new sublot efficiently, and discuss aheuristic to assign a fixed number of sublots between jobs. A model withseveral identical jobs in an multiple machine flow shop is analysed througha dominant machine approach to find optimal sublot sizes for jobs.For batch scheduling, we tackle the NP-hard problem of scheduling jobson a batching machine with restricted batch size to minimise the maximumlateness. We design a branch and bound algorithm, and develop localsearch heuristics for the problem. Different neighbourhoods are compared,one of which is an exponential sized neighbourhood that can be searched inpolynomial time. We develop dynamic programming algorithms to obtainlower bounds and explore neighbourhoods efficiently. The performance ofthe branch and bound algorithm and the local search heuristics is assessedand supported by extensive computational tests.
展开▼
