الگوریتم های هیوریستیک برای برنامه ریزی پیشگیرانه در یک فروشگاه جریان ترکیبی دو مرحله ای با منابع تجدیدپذیر اضافی در هر مرحله

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines and renewable resources at both the stages. The resource requirements are of a 0–1 type. The objective is the minimization of makespan. The problem is NP-hard. Four heuristic algorithms using linear programming are proposed for solving this problem. Performance of the algorithms is analyzed experimentally by comparing heuristic solutions with the lower bound on the optimal makespan. Statistical comparative analysis of the developed algorithms is carried out. The results of a computational experiment show that the proposed algorithms are able to produce good quality solutions in a small amount of computation time.

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines and additional renewable resource constraints at each stage. The resource requirements are of a 0–1 type. The objective is to minimize the makespan. The problem of resource constrained scheduling of parallel machines has been widely investigated in the literature (De Werra, 1984, De Werra, 1988, Figielska, 1999, Słowiński, 1980 and Słowiński, 1981). However resource constraints have not been considered until recently in the context of scheduling in the multiprocessor flowshop environment. The multiprocessor flowshop is a system which consists of a set of two or more processing centers (processing stages) with at least one center having two or more parallel machines. A job in such a system is processed successively at processing stages, and all jobs pass through the stages in the same order. At a stage with parallel machines a job can be processed on any machine and a machine can work on at most one job at a time. The multiprocessor flowshop scheduling problems have received considerable attention from researchers in recent times. Most literature in this area addresses problems with identical parallel machines and nonpreemptive jobs, and include among others Gupta, 1988, Chen, 1995, Haouari and M’Hallah, 1997, Brah and Loo, 1999 and Linn and Zhang, 1999. In our paper we focus on preemptive scheduling in a multiprocessor flowshop with unrelated machines (known as a hybrid flowshop) and additional renewable resources, where jobs require, besides machines, additional resources which are available in limited quantities at every moment. As mentioned earlier, the flowshop scheduling problem with additional renewable resources has not been studied in the literature until recently. In Figielska (2008) additional renewable resources have been taken into consideration only at the first stage of the hybrid flowshop with a single machine at the second stage. In this paper, we extend the method proposed in Figielska (2008) to the case of the flowshop with parallel unrelated machines and resource constraints at two stages. We propose four heuristic algorithms based on linear programming for solving the scheduling problem in this case. While solving the problem at the first stage, these algorithms, for the selection of jobs to be processed in parallel during successive periods of time, use selection rules appropriate for finding a minimal makespan in the whole flowshop. At the second stage, similarly as at the first stage, there are a number of parallel unrelated machines and the jobs to be processed require, besides machines, additional resources which are available in limited amounts at every moment. Each job is ready to be processed at the second stage at the moment of completing its processing at the first stage. So, given the schedule at the first stage, we have to solve the minimum makespan resource constrained scheduling problem with parallel unrelated machines and job dependent ready times (the ready times are equal to completion times at stage 1). For solving this problem to optimality, we develop a procedure based on linear programming. This procedure first determines processing times during which jobs (or parts of jobs) are executed on machines in all the time intervals between successive ready times, and then it constructs in these intervals subschedules satisfying resource constraints at every moment. The schedule in the flowshop consists of the schedule at the first stage and the schedule at the second stage. The makespan of the schedule is equal to the maximum job completion time at the second stage. Performance of the algorithms is analyzed experimentally by comparing the heuristic solutions with the lower bound on the optimal makespan. Statistical comparative analysis of the developed algorithms is carried out. The problem of scheduling in a multiprocessor flowshop arises in real-life systems that are encountered in a variety of industries, e.g. in chemical, polymer, petrochemical industries (Salvador, 1973). The multiprocessor scheduling problem is also met in computer systems and telecommunication networks (Brah, 1988). In the multiprocessor flowshop there are stages with parallel machines. At each stage with parallel machines jobs can be processed through any one of these machines. Because jobs that are simultaneously processed on parallel machines may use the same resource, the problem of resource constrained scheduling arises when the amount of the available resource is limited. This takes place when, for example, the number of workers attending the machines, or the number of tools that are used by simultaneously executed jobs, is limited. Resource requirements of a 0–1 type can be met, for example in computer systems in which one peripheral device (e.g. a printer) is additionally required to perform a job (Kellerer & Strusevich, 2002). The problems with preemptive jobs are common in the mass production of a large number of products which can be processed in parts or when an article is produced in a great amount, for example in the textile industry (Serafini, 1996) where the processing of any job (the article to be woven) on one of the parallel machines (the looms) may be interrupted (preempted) and resumed on the same or the other machine. The remainder of this paper is organized as follows. The next section contains the description of the problem we deal with. In Section 3, the heuristic algorithms are presented. An illustrative example is given in Section 4. In Section 5, a lower bound is derived. Results of a computational experiment are reported and discussed in Section 6. Section 7 summarizes the paper.

In this paper, a heuristic was proposed for solving the minimal makespan problem of preemptive scheduling in the two-stage flowshop with parallel unrelated machines and renewable resource constraints at both the stages. The heuristic first solves the problem at stage 1, sequencing jobs according to some rules, and then, using the solution at stage 1, solves the renewable resource constrained problem of scheduling unrelated machines with job dependent ready times at stage 2 (equal to the completion times at stage 1). The makespan in the flowshop is equal to the maximum completion time at stage 2. We proposed an algorithm based on linear programming which in the first step minimizes the makespan, dividing it into the time intervals determined by successive ready times. The last time interval begins at time when the last job leaves stage 1. In the second step, it constructs in every time interval a schedule which consists of a number of partial schedules. The schedule at the second stage of the flowshop with makespan determined in the first step is built from the schedules obtained for all the time intervals. Performance of the four algorithms H1–H4 which use four different rules for sequencing jobs at stage 1 was evaluated by comparing the solutions with the lower bound on the optimal makespan. We performed the detailed statistical comparison of the proposed algorithms for different machine configurations m1, m2 (m1 and m2 are the numbers of machines at stage 1 and stage 2, respectively) at both stages. It indicates which of the algorithms are most suitable for a given machine configuration. The conclusions from the statistical analysis of the results are as follows. Algorithm H3 (which assigns jobs with short minimal processing times at stage 2 to the late partial schedules in the schedule at stage 1) and algorithm H4 (which assigns jobs with short total processing times at stage 1 and the long minimal processing times at stage 2 to the partial schedules placed in the early positions in the schedule at stage 1) significantly outperform the other algorithms for machine configurations m1 < m2 and m1 = m2. Nevertheless H3 is slightly better than H4 for configuration m1 < m2 and H4 slightly outperforms H3 for configuration m1 = m2. Algorithm H2 (which assigns jobs with the short total processing times at stage 1 to the early partial schedules at stage 1) is clearly superior to the other algorithms for configuration m1 > m2. Algorithm H3, when applied to problems with m1 < m2, and algorithm H2, when used for the configuration m1 > m2, yield near-optimal solutions. Algorithm H4 produces good quality results (δ < 3.56%) for the most difficult case when m1 = m2. We studied the dependence of the effectiveness of the algorithms H1–H4 on the strength of the resource constraints for different configurations of machines at both stages. The strength of the resource constraints is connected with the value of the percentage of jobs using a resource and with the number of resource types. Different values of the percentage of jobs using a resource (5%, 15%, … , 95%) and various numbers of resource types (1, 2, … , 10) were considered. The experiment has shown that in most of the cases, the quality of solutions is better if resource constraints are stronger: We can observe an increase in deviations from optimum with increasing number of resources (decreasing strength of resource constraints) for configuration m1 = m2 and the decrease in deviations with increasing percentage of jobs using a resource (increasing strength of resource constraints) for all the configurations of machines. The quality of the results improves with the increase in the number of resources (decreasing strength of resource constrains) for configuration m1 > m2. This is due to the fact that for weaker resource constraints the schedule at the first stage with a great number of machines becomes shorter and consequently the completion times of jobs become smaller. Similar improvement in the performance can be observed for small values of the percentage of jobs using a resource (weak resource constraints) in the case of m1 = m2 and m1 > m2.