Wyniki wyszukiwania - BazTech

1

A note on hardness of multiprocessor scheduling with scheduling solution space tree

Dwibedy Debasis, Mohanty Rakesh

Computer Science

|

2023

|

T. 24 (1)

53--74

EN

We study the hardness of the non-preemptive scheduling problem of a list of independent jobs on a set of identical parallel processors with a makespan minimization objective. We make a maiden attempt to explore the combinatorial structure of the problem by introducing a scheduling solution space tree (SSST) as a novel data structure. We formally define and characterize the properties of SSST through our analytical results. We show that the multiprocessor scheduling problem is N P-complete with an alternative technique using SSST and weighted scheduling solution space tree (WSSST) data structures. We propose a non-deterministic polynomial-time algorithm called magic scheduling (MS) based on the reduction framework. We also define a new variant of multiprocessor scheduling by including the user as an additional input parameter, which we called the multiuser multiprocessor scheduling problem (MUMPSP). We also show that MUMPSP is N P-complete. We conclude the article by exploring several non-trivial research challenges for future research investigations.

2

An optimum scheduling method for multi-option product flows through production lineswithout intermediate buffers

Magiera Marek

Management and Production Engineering Review

|

2020

|

Vol. 11, No. 1

86--94

EN

The presented method is constructed for optimum scheduling in production lines with parallel machines and without intermediate buffers. The production system simultaneously performs operations on various types of products. Multi-option products were taken into account – products of a given type may differ in terms of details. This allows providing for individual requirements of the customers. The one-level approach to scheduling for multioption products is presented. The integer programming is used in the method – optimum solutions are determined: the shortest schedules for multi-option products. Due to the lack of the intermediate buffers, two possibilities are taken into account: no-wait scheduling, possibility of the machines being blocked by products awaiting further operations. These two types of organizing the flow through the production line were compared using computational experiments, the results of which are presented in the paper.

3

Scheduling battery charging jobs with linearly decreasing power demands to minimize the total time

Różycki R., Waligóra G., Węglarz J.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2020

|

Vol. 68, nr 2

299--306

EN

In this work we consider a problem from the field of power- and energy-aware scheduling, in which a set of batteries have to be charged in a minimum time. The formulated problem is to schedule independent and nonpreemptable jobs to minimize the schedule length, where each job requires some amount of power and consumes a certain amount of energy during its processing. We assume that the power demand of each job linearly decreases with time, as it is the case when Li-ion batteries are being charged. For the assumed job model we prove that each next job should be started as soon as the required amount of power is available. Basing on the proven theorem we formulate a procedure generating a minimum-length schedule for an assumed order of jobs. We also analyze the case of identical jobs, and show some interesting properties of this case.

4

Particle swarm optimization and discrete artificial bee colony algorithms for solving production scheduling problems

Witkowski Tadeusz

Technical Sciences / University of Warmia and Mazury in Olsztyn

|

2019

|

nr 22(1)

61--74

EN

This paper shows the use of Discrete Artificial Bee Colony (DABC) and Particle Swarm Optimization (PSO) algorithm for solving the job shop scheduling problem (JSSP) with the objective of minimizing makespan. The Job Shop Scheduling Problem is one of the most difficult problems, as it is classified as an NP-complete one. Stochastic search techniques such as swarm and evolutionary algorithms are used to find a good solution. Our objective is to evaluate the efficiency of DABC and PSO swarm algorithms on many tests of JSSP problems. DABC and PSO algorithms have been developed for solving real production scheduling problem too. The experiment results indicate that this problem can be effectively solved by PSO and DABC algorithms.

5

Exploring heuristic techniques for flow shop scheduling

Soltysova Zuzana, Semanco Pavol, Modrak Jan

Management and Production Engineering Review

|

2019

|

Vol. 10, No. 3

54–-60

EN

This paper explores selected heuristics methods, namely CDS, Palmer’s slope index, Gupta’s algorithm, and concurrent heuristic algorithm for minimizing the makespan in permutation ﬂow shop scheduling problem. Its main scope is to explore how diﬀerent instances sizes impact on performance variability. The computational experiment includes 12 of available benchmark data sets of 10 problems proposed by Taillard. The results are computed and presented in the form of relative percentage deviation, while outputs of the NEH algorithm were used as reference solutions for comparison purposes. Finally, pertinent ﬁndings are commented.

6

Management of mass customized orders using flexible schedules to minimize delivery times

Pandian R. S., Soltysova Z.

Polish Journal of Management Studies

|

2018

|

Vol. 18, No. 1

252--261

EN

The goal of mass customization is to make the products and / or services to satisfy individual customer who makes the order with a specific design for their needs. In real situation it is not so easy deal to meet individual design and to satisfy each customer separately; there is a need to accustom such environment to fulfill the market demand. In such situation, the decision makers are to ensure that they are following flexibility while taking orders and also dispatching them to the customers. One such idea is being developed in this research work. The main aim of this research work is to offer the procedure; flexible mass customization (FLMACUS) to make flexible schedules that meets the customer requirements. A simple heuristics is used to develop the procedure and Gantt charts are used for accommodating the jobs for meeting specific due dates. In this paper batch type Original Equipment Manufacturers (OEMs) are considered for our study purpose. The results from Gantt charts in various categories are depicted. Such types of Gantt charts are hardly found in earlier studies and the results show that this procedure (FLMACUS) is promising in nature to meet customer demands and due dates in a mass customized environment.

PL

Celem masowej personalizacji jest sprawienie, aby produkty i / lub usługi satysfakcjonowały indywidualnego klienta, który dokonuje zamówienia zgodnego z konkretnym projektem odpowiadającego jego potrzebom. W rzeczywistej sytuacji nie jest łatwo znaleźć indywidualny projekt i zadowolić każdego klienta osobno; istnieje potrzeba przystosowania takiego środowiska do zaspokojenia popytu na rynku. W takiej sytuacji decydenci muszą upewnić się, że działają elastycznie przy przyjmowaniu zamówień i wysyłaniu ich do klientów. Taka koncepcja rozwinięta została w niniejszej pracy badawczej. Głównym celem badania jest zaproponowanie procedury; elastyczną masową personalizację (FLMACUS) do tworzenia elastycznych harmonogramów spełniających wymagania klientów. Do opracowania procedury wykorzystano prostą heurystykę, natomiast do dostosowania zadań do spełnienia określonych terminów posłużyły wykresy Gantta. W artykule do celów badawczych wzięto pod uwagę Producentów Oryginalnego Sprzętu (OEM). W kolejnej części artykułu przedstawiono wyniki z wykresów Gantta w różnych kategoriach. Tego typu wykresy Gantta prawie nie występują we wcześniejszych badaniach, a wyniki pokazują, że ta procedura (FLMACUS) ma charakter obiecujący, aby sprostać wymaganiom klientów i terminom w masowo dostosowywanym środowisku.

7

Comparative simulation study of production scheduling in the hybrid and the parallel flow

Varela M. L. R., Trojanowska J., Carmo-Silva S., Costa N. M. L., Machado J.

Management and Production Engineering Review

|

2017

|

Vol. 8, No. 2

69--80

EN

Scheduling is one of the most important decisions in production control. An approach is proposed for supporting users to solve scheduling problems, by choosing the combination of physical manufacturing system configuration and the material handling system settings. The approach considers two alternative manufacturing scheduling configurations in a two stage product oriented manufacturing system, exploring the hybrid flow shop (HFS) and the parallel flow shop (PFS) environments. For illustrating the application of the proposed approach an industrial case from the automotive components industry is studied. The main aim of this research to compare results of study of production scheduling in the hybrid and the parallel flow, taking into account the makespan minimization criterion. Thus the HFS and the PFS performance is compared and analyzed, mainly in terms of the makespan, as the transportation times vary. The study shows that the performance HFS is clearly better when the work stations’ processing times are unbalanced, either in nature or as a consequence of the addition of transport times just to one of the work station processing time but loses advantage, becoming worse than the performance of the PFS configuration when the work stations’ processing times are balanced, either in nature or as a consequence of the addition of transport times added on the work stations’ processing times. This means that physical layout configurations along with the way transport time are including the work stations’ processing times should be carefully taken into consideration due to its influence on the performance reached by both HFS and PFS configurations.

8

Scheduling preemptable jobs on identical processors under varying availability of an additional continuous resource

Różycki R., Waligóra G., Węglarz J.

International Journal of Applied Mathematics and Computer Science

|

2016

|

Vol. 26, no. 3

693--706

EN

In this work we consider a problem of scheduling preemptable, independent jobs, characterized by the fact that their processing speeds depend on the amounts of a continuous, renewable resource allocated to jobs at a time. Jobs are scheduled on parallel, identical machines, with the criterion of minimization of the schedule length. Since two categories of resources occur in the problem: discrete (set of machines) and continuous, it is generally called a discrete-continuous scheduling problem. The model studied in this paper allows the total available amount of the continuous resource to vary over time, which is a practically important generalization that has not been considered yet for discrete-continuous scheduling problems. For this model we give some properties of optimal schedules on a basis of which we propose a general methodology for solving the considered class of problems. The methodology uses a two-phase approach in which, firstly, an assignment of machines to jobs is defined and, secondly, for this assignment an optimal continuous resource allocation is found by solving an appropriate mathematical programming problem. In the approach various cases are considered, following from assumptions made on the form of the processing speed functions of jobs. For each case an iterative algorithm is designed, leading to an optimal solution in a finite number of steps.

9

Scheduling arbitrary number of malleable tasks on multiprocessor systems

Barketau M. S., Kovalyov M. Y., Węglarz J., Machowiak M.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2014

|

Vol. 62, nr 2

255--261

EN

The problem of scheduling n tasks in a multiprocessor system with m processors to minimize the makespan is studied. Tasks are malleable, which means that a task can be executed by several processors at a time, its processing speed depends on the number of allocated processors, and a set of processors allocated to the same task can change over time. The processing speed of a task is a strictly increasing function of the number of processors allocated to this task. The earlier studies considered the case n ≤ m. This paper presents results for arbitrary n and m including characterizations of a feasible domain and an optimal solution, polynomial time algorithms for strictly increasing convex and concave processing speed functions, and a combinatorial exponential algorithm for arbitrary strictly increasing functions.

10

Effective Design of the Simulated Annealing Algorithm for the Flowshop Problem with Minimum Makespan Criterion

Hurkała J., Hurkała A.

Journal of Telecommunications and Information Technology

|

2012

|

nr 2

92-98

EN

In this paper we address the n-job, m-machine flowshop scheduling problem with minimum completion time (makespan) as the performance criterion. We describe an efficient design of the Simulated Annealing algorithm for solving approximately this NP-hard problem. The main difficulty in implementing the algorithm is no apparent analogy for the temperature as a parameter in the flowshop combinatorial problem. Moreover, the quality of solutions is dependent on the choice of cooling scheme, initial temperature, number of iterations, and the temperature decrease rate at each step as the annealing proceeds. We propose how to choose the values of all the aforementioned parameters, as well as the Boltzmann factor for the Metropolis scheme. Three perturbation techniques are tested and their impact on the solutions quality is analyzed. We also compare a heuristic and randomly generated solutions as initial seeds to the annealing optimization process. Computational experiments indicate that the proposed design provides very good results - the quality of solutions of the Simulated Annealing algorithm is favorably compared with two different heuristics.

11

Problem-Independent Approach to Multiprocessor Dependent Task Scheduling

Król D., Zydek D., Koszałka L.

International Journal of Electronics and Telecommunications

|

2012

|

Vol. 58, No. 4

369-379

EN

This paper concerns Directed Acyclic Graph task scheduling on parallel executors. The problem is solved using two new implementations of Tabu Search and genetic algorithm presented in the paper. A new approach to solution coding is also introduced and implemented in both metaheuristics algorithms. Results given by the algorithms are compared to those generated by greedy LPT and SS-FF algorithms; and HAR algorithm. The analysis of the obtained results of multistage simulation experiments confirms the conclusion that the proposed and implemented algorithms are characterized by very good performance and characteristics.

12

A two-stage flow shop scheduling with a critical machine and batch availability

Gerstl E., Mosheiov G.

Foundations of Computing and Decision Sciences

|

2012

|

Vol. 37, No. 1

39-56

EN

We study a two-stage flowshop, where each job is processed on the first (critical) machine, and then continues to one of two second-stage (dedicated) machines. We assume identical (but machine-dependent) job processing times. Jobs are processed on the critical machine in batches, and a setup time is required when starting a new batch. The setting assumes batch-availability, i.e., jobs become available for the second stage only when their entire batch is completed on the critical machine. We consider three objective functions: minimum makespan, minimum total load, and minimum weighted flow-time. Polynomial time dynamic programming algorithms are introduced, which are numerically shown to be able to solve problems of medium size in reasonable time. A heuristic for makespan minimization is presented and shown numerically to be both accurate and efficient.

13

On Recent Modifications And Extensions Of The Neh Heuristic For Flow Shop Sequencing

Kalczyński P.J., Kamburowski J.

Foundations of Computing and Decision Sciences

|

2011

|

Vol. 36, No. 1

18-33

EN

Until recently, the NEH heuristic of Nawaz, Enscore and Ham published in j 1983 was commonly regarded as the best constructive heuristic for solving the classic j strongly NP-hard problem of minimizing the makespan in permutation flow shops. The I long-lasting success of NEH inspired many researchers to propose improvements to the original heuristic. In this paper, we empirically examine recent modifications and extensions of NEH and present a heuristic for the permutation flow shop problem which incorporates components from the best proposals. The performance of analyzed heuristics is evaluated with respect to the improvement over NEH and additional computational time required to achieve this improvement.

14

A new approach to job shop-scheduling problem

Mahdavinejad R. A.

Journal of Achievements in Materials and Manufacturing Engineering

|

2010

|

Vol. 41, nr 1-2

200-206

EN

Purpose: Ant colony optimization algorithm, not only promote the ability of this proposed algorithm, but also de- creases the total working time because of decreasing in setup times and modifying the working production line. Design/methodology/approach: In this paper, single-processors jobshop scheduling problems are solved by a heuristic algorithm based on the hybrid of priority dispatching rules according to an ant colony optimization algorithm. Findings: The objective function is to minimize the makespan, i.e. total completion time, in which a simultanous presence of various kinds of ferons is allowed. The process of finding the best solution will be improved by using the suitable hybrid of priority dispatching rules. Research limitations/implications: By solving some problems as samples (i.e. Fisher’s & Tomson’s problems), this algorithm is compared with the others. Practical implications: The utilization of one processor instead of multiple one, merging the industrial control network layer into system management layer and omission of processor execution layer in each axis and optimized using of multi-tasking capability of processor. Originality/value: The results show that when the size of the problem becomes larger, the deviation from lower limit increases, but its rate decreases with the size of the problems, so that it reaches to its limit.

15

On a bicriteria optimal production plan

Kuchta D.

Control and Cybernetics

|

2007

|

Vol. 36, no 2

357-366

EN

The classical mathematical programming problem used for the determination of a production plan maximising total income or profit is complemented with a second objective, concerning the makespan of the products being manufactured on two machines. As a result, a bicriterial integer linear programming problem is obtained, which can be solved by means of classical methods. A computational example is presented and discussed.

16

Lower bounds for the scheduling problem with uncertain demands

Berkoune D., Mesghouni K., Rabenasolo B.

International Journal of Applied Mathematics and Computer Science

|

2006

|

Vol. 16, no 2

263-269

EN

This paper proposes various lower bounds to the makespan of the flexible job shop scheduling problem (FJSP). The FJSP is known in the literature as one of the most difficult combinatorial optimisation problems (NP-hard). We will use genetic algorithms for the optimisation of this type of problems. The list of the demands is divided in two sets: the actual demand, which is considered as certain (a list of jobs with known characteristics), and the predicted demand, which is a list of uncertain jobs. The actual demand is scheduled in priority by the genetic algorithm. Then, the predicted demand is inserted using various methods in order to generate different scheduling solutions. Two lower bounds are given for the makespan before and after the insertion of the predicted demand. The performance of solutions is evaluated by comparing the real values obtained on many static and dynamic scheduling examples with the corresponding lower bounds.

17

An on-line algorithm for the bounded p-batch scheduling with chain precedence constraints and unit processing time

Nong Q., Yuan J.

Foundations of Computing and Decision Sciences

|

2006

|

Vol. 31, No. 3-4

277-290

EN

We consider the problem of scheduling unit time jobs with release dates on a single machine which can process up to b jobs simultaneously as a batch under on-line setting. There are chain precedence constraints on the jobs. The release dates and the precedence relations of the jobs remain unknown until their arrivals. The scheduling problem involves assigning all the jobs to batches and determining the starting times of the batches in such a way that the maximum completion time of the jobs (makespan) is minimized. In this paper we present an on-line algorithm with a worst-case ratio of radic3 for the problem.