Wyniki wyszukiwania - BazTech

1

Algorithms Using List Scheduling and Greedy Strategies for Scheduling in the Flowshop with Resource Constraints

Figielska E.

Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki

|

2014

|

nr 11

29--39

EN

The paper addresses the problem of scheduling in the two-stage flowshop with parallel unrelated machines and renewable resource constraints. The objective is minimization of makespan. The problem is NP-hard. Fast heuristic algorithms using list scheduling and greedy strategies are proposed. For evaluation of the performance of the algorithms computational experiments are performed on randomly generated test problems, and results are reported.

2

Cost-efficient project management based on critical chain method with partial availability of resources

Pawiński G., Sapiecha K.

Control and Cybernetics

|

2014

|

Vol. 43, no. 1

95--109

EN

Cost-efficient project management based on Critical Chain Method (CCPM) is investigated in this paper. This is a variant of the resource-constrained project scheduling problem (RCPSP) when resources are only partially available and a deadline is given, but the cost of the project should be minimized. RCPSP is a well- known NP hard problem but originally it does not take into consideration the initial resource workload. A metaheuristic algorithm driven by a metric of a gain was adapted to solve the problem when applied to CCPM. Refinement methods enhancing the quality of the results are developed. The improvement expands the search space by inserting the task in place of an already allocated task, if a better allocation can be found for it. The increase of computation time is reduced by distributed calculations. The computational experiments showed significant efficiency of the approach, in comparison with the greedy methods and with genetic algorithm, as well as high reduction of time needed to obtain the results.

3

An Ant Colony Optimization Algorithm for Scheduling Parallel Machines with Sequence-Dependent Setup Costs

Figielska E.

Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki

|

2013

|

nr 9

15--26

EN

The paper addresses the problem of scheduling preemptive jobs on parallel unrelated machines in the presence of renewable resource constraints and sequence-dependent setup costs. The objective is to minimize the weighted sum of makespan and setups. The problem is known to be NP-hard. To solve this problem, a heuristic is proposed which uses column generation technique and an ant colony optimization algorithm. The results of a computational experiment indicate that the heuristic is able to produce good results in reasonable computation time.

PL

Artykuł dotyczy zagadnienia szeregowania zadań podzielnych na równoległych dowolnych maszynach z uwzględnieniem ograniczeń na dostępność zasobów odnawialnych oraz kosztów przezbrojeń zależnych od kolejności wykonywania zadań. Celem jest minimalizacja ważonej sumy czasu trwania harmonogramu i przezbrojeń. Zagadnienie należy do klasy problemów NP-trudnych. W celu jego rozwiązania, zaproponowany został algorytm heurystyczny, wykorzystujący technikę generacji kolumn, oraz algorytm mrówkowy. Wyniki eksperymentu obliczeniowego wskazują, że algorytm ten jest zdolny dostarczyć dobrej jakości wyniki w rozsądnym czasie.

4

Linear programming & metaheuristic approach for scheduling in the hybrid flowshop with resource constraints

Figielska E.

Control and Cybernetics

|

2011

|

Vol. 40, no 4

1209-1230

EN

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines and additional renewable resources. The objective is the minimization of makespan. The problem is NP-hard. Heuristic algorithms are proposed which join the linear programming based procedures with metaheuristic algorithms: genetic, simulated annealing and tabu search algorithm. The performance of the proposed algorithms is experimentally evaluated by comparing the solutions with a lower bound on the optimal makespan. Results of a computational experiment show that these algorithms are able to produce good solutions in short computation time and that the metaheuristics significantly improve the results for the most difficult problems.

5

A genetic algorithm for the project scheduling with the resource constraints

Klimek M.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

|

2010

|

Vol. 10, no. 1

117--130

EN

The resource-constrained project scheduling problem (RCPSP) has received the attention of many researchers because it can be applied in a wide variety of real production and construction projects. This paper presents a genetic algorithm (GA) solving the RCPSP with the objective function of minimizing makespan. Standard genetic algorithm has to be adapted for project scheduling with precedence constraints. Therefore, an initial population was generated by a random procedure which produces feasible solutions (permutation of jobs fulfilling precedence constraints). Besides, all implemented genetic operators have taken sequential relationships in a project into consideration. Finally, we have demonstrated the performance and accuracy of the proposed algorithm. Computational experiments were performed using a set of 960 standard problem instances from Project Scheduling Problem LIBrary (PSPLIB) presented by Kolisch and Sprecher [1]. We used 480 problems consisting of 30 jobs and 480 90-activity instances. We have tested effectiveness of various combinations of parameters, genetic operators to find the best configuration of GA. The computational results validate the good effectiveness of our genetic algorithm.

6

Heuristic algorithms for preemptive scheduling in a Two-stage flowshop with unrelated parallel machines and 0-1 resource requirements

Figielska E.

Control and Cybernetics

|

2009

|

Vol. 38, no 3

723-743

EN

The paper considers the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines at the first stage and a single machine at the second stage. At the first stage, jobs use some additional renewable resources which are available in limited quantities. The resource requirements are of 0-1 type. The objective is minimization of the makespan. The problem is NP-hard. We develop heuristic algorithms which first solve the problem occurring at stage 1, and then find a final schedule in the flowshop. An extensive computational experiment shows that the proposed heuristic algorithms can be an efficient tool capable of finding good quality solutions.

7

Planowanie przedsięwzięć w warunkach czasowych ograniczeń dostępu do zasobów

Banaszak Z., Knosala R., Pisz I., Tomczuk I.

Zarządzanie Przedsiębiorstwem

|

2003

|

Vol. 6, nr 2

4-14

EN

The paper addresses an issue of decision-making support for project-driven small and medium size enterprises. The considered problem regards of finding a feasible schedule that follows the constraints imposed by duration order and price selling given by customer and by the time-constrained resources availability. In other words it is looking for the answer whether a given work order can be accepted for processing in an manufacturing system. The problem belongs to a class of multi-mode case problems of a project scheduling, where finding of a feasible solution is NP-complete. In that context the main constraints of commercially available packages, e.g. MS PROJECT 2002, PROJECT SCHEDULER 6.0, ProAlpha l ,4d, ILOG OPL Studio 3.6 are discussed. In order to overcome the disadvantages observed a new heuristic project scheduling method is proposed and its software implementation is presented as well.