Developing feasible and optimal schedules of jobs on one machine
- PDF / 178,363 Bytes
- 16 Pages / 595.276 x 793.701 pts Page_size
- 71 Downloads / 166 Views
DEVELOPING FEASIBLE AND OPTIMAL SCHEDULES OF JOBS ON ONE MACHINE UDC 519.2
Yu. A. Zack
Abstract. The paper considers the properties of feasible and optimal scheduling of jobs on one machine under constraints on the terms of the beginning and completion of jobs and on partial sequences of job performance. The established properties and the lower-bound estimates of the length of the optimal schedule are used to develop methods for the exact and approximate solutions of the formulated problem by sequential optimization algorithms. The proposed algorithms are illustrated by numerical examples and can be successfully applied to solve these problems in the absence of constraints. Keywords: optimal schedule, job sequencing, makespan constraints, sequential optimization algorithms. INTRODUCTION Monographs and periodicals on scheduling theory pay much attention to the optimal sequencing of n jobs executed by one machine. The problem under study specifies makespan constraints t i for the start date a i and the end date g i , necessary to complete each job after its processing by the given machine. All the values of t i , a i , and g i , i = 1,... , n , are integer numbers. It is necessary to determine the optimal sequence L of processing all the jobs on this machine and the time of the beginning x i and the end s i of each job. The optimal schedule should ensure all the above constraints and minimize the latest end date taking into account the time necessary to complete the processing of each job on other machines, g i . For the formulated problem (NP-hard, as shown in [1]), rather efficient solution algorithms are proposed (see, for example, [2–10]), which allow finding exact and approximate solutions to practical problems of rather high dimensions. Efficient algorithms for exact problem solution by the Schrage algorithm and its modifications were proposed first by J. Carlier in [5] in 1982 and developed in [6, 7]. These algorithms are most often applied to obtain exact solutions to high-dimensional practical problems. However, for practical applications of scheduling the production, service management, and computation process, of great importance is to formulate the problem of developing a feasible schedule (sequence) of jobs executed on one machine that accounts for the constraints imposed on the end date of each job d i , i = 1,... , n , and some fixed orders specified by the precedence of some subsets of jobs before others. Additional conditions are assumed to be satisfied: (a) none job can be interrupted during the execution and no more than one job can be executed on the machine. The problem under study, as well as the well-known one-machine sequencing problem [1–10] is NP-hard. Under these additional constraints, the author is not aware of efficient solution algorithms for the formulated problems that would allow solving high-dimensional problems with the same amount of calculation as methods [5–7] do. The present paper proposes another approach (distinct from that considered in [5–7]) to the solution of the formul
Data Loading...
