Some studies in location and scheduling problems

Abstract

The location and scheduling problems considered in this study are special cases of what are called combinatorial models. A combinatorial optimization problem consists of finding, from among a finite set of alternatives, one that optimizes the value of an objective function. For example, the job shop scheduling, concentrator location, and Traveling Salesman Problems considered in this study involve choosing the best schedule, location, and tour respectively from a finite set of alternatives. There is no general method for solving all combinatorial problems. It is true that, with sufficient ingenuity, it is always possible to devise a non-trivial integer programming representation of a combinatorial optimization problem. Frequently, such integer programming problems are very large (that is, there are an enormous number of constraints and variables), and therefore the formulation is of negligible computational interest. So it is necessary to study different combinatorial models separately and devise algorithms for these special cases. Several models of different degrees of abstraction have been studied and solution methods developed. This has helped in increasing the understanding of scheduling and location problems considerably in recent years. Because this ad hoc approach has been so successful, the same has been adopted in this study also. The first two chapters of this study deal with job shop scheduling problems, the third deals with the TSP (Traveling Salesman Problem), and in the fourth chapter, two algorithms for a location problem have been presented. The individual chapters will be considered in detail now.

Scheduling with Finite Storage and Ordered Processing Matrix The job-machine scheduling problem with finite storage is considered. There are no due dates or priorities, and the sole objective is to complete all the jobs in the least time. All jobs have to be processed on all the machines. It is assumed that the buffers between any two machines have finite capacity (finite storage). This problem is an unsolved one. A special case of this problem, solved here, arises when the processing matrix (matrix of processing times) is ordered. The processing matrix is said to be ordered if the following condition is satisfied: If pi<pjp_i < p_jpi?<pj?, then for k=1,...,nk = 1, ..., nk=1,...,n, and if pj<pkp_j < p_kpj?<pk?, then pi<pkp_i < p_kpi?<pk? for i=1,...,Mi = 1, ..., Mi=1,...,M, where pjkp_{jk}pjk? is the processing time of job jjj on machine kkk. The ordered problems occur in practice due to several reasons, one of them being job complexity. In this study, the finite storage, ordered processing matrix problem has been considered and the following results obtained. Let SSS be the number of jobs that can wait between any two machines. Let VkV_kVk? be the completion time of the sequence of jobs on the kkk-th machine. Then when pi<pjp_i < p_jpi?<pj?, the results are derived for the case M=2M = 2M=2. They can be extended to the general case in a straightforward way. The following is proved: i) There is an optimal sequence for the 2-machine finite storage scheduling problem with ordered processing matrix in which the first S+2S + 2S+2 jobs are in the ascending order of processing times. ii) There exists an optimal sequence in which the last job has the largest processing time. iii) When the jobs are numbered in the ascending order of processing times, and all the jobs j?kj \geq kj?k are greater than or equal to kkk, and all jobs j<kj < kj<k are <k< k<k, the following has been proved: i) There is an optimal sequence in which the last S+2S + 2S+2 jobs must be in the descending order of processing times. ii) There is an optimal sequence in which the first job is the one which has the largest processing time. iii) When the jobs are numbered in the ascending order of processing times, the above results are used to obtain the optimal schedule.