An investigation into approximate solutions for deterministic and stochastic multi-dimensional sequencing

We investigate the problem that involves sequencing jobs having multiple components. Each component of the job needs to be processed independently on specified machine. We derive approximate algorithms for the problem of scheduling such vector jobs to minimize their total completion time in the deterministic as well as stochastic setting. In particular, we propose an LP based and a greedy strategy. The LP based approach is an extension of (Sivasubramanian, 2003) to adapt Potts’ formulation (Potts, 1980; Hall et al., 1996) for single component job scheduling. We propose bounds on the performance ratio of the two approaches for deterministic and stochastic formulation of the problem. 1 Problem Description The ideas for the approaches discussed in this paper arose during the investigation of a practical problem faced by a composite-bearings manufacturer. Manufacturing a composite bearing initially requires the individual components to be built. Such components include ball bearings, needle bearings and shaft bearings. The components are typically processed independently on different machines and then assembled together. Each machine requires to be configured uniquely to make a given component. The machines may be regarded as suppliers supplying basic commodities. The bearings-assembly process can similarly be regarded as a manufacturer which “manufactures” end-products using the supplied basic commodities. Such models of interaction have been studied recently in (Chen and Hall, 2005; Potts et al., 1995). The results of (Chen and Hall, 2005) throw light on the lower bound on the performance guarantees, whereas in this ? The work was funded by the Engineering and Physical Sciences Research Council’s (U.K) grant number EP/C500148/1. paper we study upper bounds on the worst case performance ratios. Potts’ article (Potts et al., 1995) investigate different objective criteria, e.g. minimizing the makespan. Each job corresponding to the manufacturing of a composite-bearing can be looked upon as a vector. The completion time of a job is defined as the maximum time taken to complete its components. The problem is to schedule the vectors of jobs such that the sum of the completion times of all the jobs is minimised. We consider deterministic and stochastic formulation of the vector job scheduling problem. In the stochastic formulation we assume that the completion time of the tasks on the machines are random variables. The results of (Sivasubramanian, 2003; Hall, 1998) have already established the NP-hardness of this problem. Therefore, it is justified to study the approximation algorithms and general heuristic approaches to solve this problem. We discuss approximate solutions using a greedy and an LP based method for the deterministic and stochastic formulation of vector job scheduling problem. 1.1 Problem definition INDICES n = number of jobs, m = number of machines, i,j= indices over the number of jobs, k= index over the number of machines, DATA pi = processing time taken to complete the k th component of i job, pi ≥ 0. Ji = the i job, defined as (pi , p 2 i , . . . , p m i ), J = set of jobs = {J1, J2, . . . Jn} VARIABLES Π = schedule for the vector jobs (described by a permutation of {1, 2, . . . n}), Πi = the i job of the schedule given by the permutation Π, CΠi = time taken to complete the i th job in the schedule Π, C = time taken to complete all the jobs. OBJECTIVE Minimise C. CONSTRAINTS k machine can process only k component of each job. The value CΠi is equal to the sum of the completion time for all the jobs preceeding and including over i job, CΠi = m max k=1 { i ∑