الگوریتم ابتکاری برای برنامه ریزی کاهش انتظار جریان فروشگاه

Sequencing and scheduling are forms of decision making which play a key role in manufacturing. This paper presents the description of a scheduling algorithm for the solution of the no-wait flow-shop problem. The goal of the heuristic is to minimise the sum of the total flow-times, a criterion which at the same time minimises the average processing time. This is a sensible target in applications such as agile manufacturing where jobs are constantly added to the job list. When evaluated over a large number of problems of various sizes, the heuristic is found to be very effective in yielding near-optimal solutions

Scheduling is concerned with setting the timetable for the processing of a given set of jobs on a set of machines in order to optimise a given measure of performance. Many researchers have proposed approaches for solving these problems which have an immediate application in many fields of manufacturing. The large number of publications in this area is related to the fact that there is an enormous number of different characteristics and objectives according to the environment to schedule, associated with a wide choice of the parameters to optimise. Pinedo [13] offers a comprehensive review on optimisation and heuristic methods in production scheduling. Scheduling algorithms are usually designed to solve special problems involving constraints on jobs and scheduling objectives [12]. Different problems may be characterised by different flow patterns of the jobs. The flow pattern may be the same for all the jobs (flow-shop), or each job may have its own individual flow pattern (job-shop), or no specified flow pattern may exist (open-shop). Parallel or duplicated machines may be present. Within these environments, the goal is to find a schedule which tries to optimise a specified objective, such as the completion time, the tardiness, or the flow-time of the jobs. In many manufacturing cells, there is the constraint that all the jobs have to follow the same path, and that once a job is started it must be processed until completion without any interruption either on or between machines. Such a flow-shop is usually called no-wait flow-shop. This type of scheduling is necessary where operations are required to follow one immediately after the other due to production constraints, such as during the production of steel or plastic moulding. In addition, modern manufacturing environments such as agile manufacturing, where robots and industrial machines provide a highly coordinated process, can frequently be modelled as a no-wait scheduling problem. A comprehensive review on the state of the art in this area of scheduling is presented in [9]. This paper focuses on the objective of minimising the sum of all completion times of the jobs in a no-wait flow-shop. This scheduling problem can be synthetically denoted as an Fm|no-wait|∑Cj problem, where Fm indicates a flow-shop problem with m devices, and Cj is the completion time of the job j. Minimising the total flow-time is equivalent to minimising the sum of completion times, and consequently the average processing time. In other terms, the aim of the algorithm is to finish each job as soon as possible. This is an appropriate criterion in the case of manufacturing workcells, where minimising the average time for completing a job is a sensible target since new jobs are constantly added to the job list. At present, there are only a few available algorithms which have been proposed for solving this problem. Van Deman and Baker [6] proposed a branch and bound approach to find the optimal solution proposing a set of procedures for generating lower bounds on optimal values. Heuristic algorithms have also been proposed by Rajendran and Chauhuri [14] and Gangadharan and Rajendran [7]. These algorithms produce better schedules when compared with the ones derived using the heuristics developed by Bonney and Gundry [3] and King and Spachis [11]. The theoretical aspects of the continuous flow-shop have been investigated by Gupta [8], Szwarc [15], and Adiri and Pohoryles [1]. This article presents a heuristic algorithm based on job insertion for the no-wait flow-shop problem whose aim is to minimise total flow-time starting from a suboptimal sequence. The main idea of the proposed heuristic is to improve the results of the schedules generated using the heuristic described in [2] by using them as a starting point for a job insertion algorithm as described in the work of Rajendran and Chauhuri [14]. The remainder of the paper is structured as follows. Section 2 presents the foundations of the proposed heuristic approach. Section 3 exemplifies the proposed algorithm using a simple scheduling problem. Section 4 reports the details of the computational experience and a comparison of the performance of our algorithm with earlier proposed heuristics. Finally, Section 5 will present some final comments on the presented approach.

A heuristic for scheduling in the no-wait flow-shop has been developed in this paper. It is based on a job pair comparison approach that generates a sequence of jobs which is then improved by a job insertion algorithm. The procedure behind the definition of the job sequence which is passed to the job insertion algorithm is simple to use and to understand, and generates consistent meaningful schedules which are suitable for further improvement. After extensive computational experiences, it has been found that the proposed heuristic provides near-optimal solutions, which are generally better than the ones provided by other existing heuristics. This is obtained using the same order of computational load than other high performing approaches.