Wyniki wyszukiwania - BazTech

1

A Batching Machine Model for Lot Scheduling on a Single Machine

Kovalyov M. Y.

Foundations of Computing and Decision Sciences

|

2018

|

Vol. 43, No. 1

38--40

EN

A recently introduced lot scheduling problem is considered. It is to find a partition of jobs of n orders into lots and to sequence these lots on a single machine so that the total average completion time of the orders is minimized. A simple O(n log n) time algorithm is presented for this problem in the literature, with a relatively sophisticated proof of its optimality. We show that modeling this problem as a classic batching machine problem makes its optimal solution obvious.

2

An exact block algorithm for no-idle RPQ problem

Pempera J.

Archives of Control Sciences

|

2017

|

Vol. 27, no. 2

323--330

EN

In the work a single-machine scheduling problem is being considered, in which all tasks have a fixed availability (release) and delivery time. In the analyzed variant no-idle time is allowed on a machine. The purpose of optimization is to determine such order of tasks that minimizes the makespan, i.e. the time of execution of all the tasks. There is also a number of properties of the problem presented, in particular there are formulated block eliminating properties for no-idle constraint. There was an exact B&B algorithm based on the block properties proposed.

3

Sposób szeregowania zadań dla jednej maszyny o ograniczonych zasobach

Cechowicz R.

Pomiary Automatyka Kontrola

|

2011

|

R. 57, nr 9

1093-1096

PL

W artykule opisano system szeregowania zadań niepodzielnych na jednej maszynie. System pozwala zoptymalizować plan produkcji poprzez ograniczenie ilości operacji transportowych i pomocniczych oraz poprzez poszukiwanie takiej kolejności realizacji zadań, dla której łączny czas wykonania będzie możliwie najmniejszy. Zastosowano zmodyfikowany algorytm genetyczny pozwalający na częściowe dostrojenie procesu do struktury danych. Testy przeprowadzone zarówno na danych dostępnych publicznie, jak i na danych pochodzących ze środowiska wytwórczego udowodniły skuteczność przyjętych rozwiązań.

EN

A system for scheduling indivisible tasks on a single, periodically accessible machine is presented in this paper. Because of the constrains existing in the environment, the scheduling problem presented here is similar to the one-dimensional bin-packing. The tasks, stacked on a palettes (Fig.1), were transported to the machine. The palette caould be replaced by another one only after completing all the tasks assigned to it. Each task was defined by an execution time Tz and an auxiliary time Tp. The transportation time To was added to the last task from each palette and to the last task executed within the machine availability period Tm (Fig.2). A modified genetic algorithm was used for the scheduling, where the parameter K defined the number of gene changeovers (representing changing the sequence of palettes and changing the sequence of tasks within a palette) during one mutation. The results obtained for the data available in public [13] and in selected publications are presented in Tab.1. It was noted that the distribution of scheduling results (fitness=Cmax) could be modified by changing the parameter K (Figs.4 and 6). The observation was proved statistically for the data from the manufacturing system by means of the median test run for the set of 500 results, 50 for each K=1..10 (χ2=19, df=9, p=0,0254<0,05). The results of the test proved that the scheduling algorithm could be tuned for speed by adjusting the value of K. Assuming that the process was random, it could be calculated that for K=5 the expected time of getting the solution Cmax<2050, expressed in the number of generations, was the shortest (assumed confidence level 0.99). The scheduling system allowed the definition of individual machine availability periods and taking into account the restrictions of the transport system (the allowed sequences of palette retrieval).

4

Scheduling jobs with linear model of simultaneous ageing and learning effects

Janiak A., Lichtenstein M., Rusoń A.

Decision Making in Manufacturing and Services

|

2011

|

Vol. 5, no. 1-2

37-48

EN

In the paper, we introduce some new scheduling model in which learning and aging effects are both considered simultaneously. In this model the actual processing time of the jobs depends only on its position in a schedule and can be described by the piecewise linear function. For single-processor problem with introduced model, we show that the problem of minimizing the makespan criterion for independent jobs with release dates is strongly NP-hard, but some special cases of this problem are polynomially solvable. Based on those special cases, we propose 4 heuristic algorithms and we experimentally examine their usefulness for solving the general problem.

5

A new optimal algorithm for a time-dependent scheduling problem

Kubale M., Ocetkiewicz K. M.

Control and Cybernetics

|

2009

|

Vol. 38, no 3

713-721

EN

In this article a single machine time-dependent scheduling problem with total completion time criterion is considered. There are n given jobs, j1,...,jn, and the processing time pi of the i-th job is given by pi = 1 + biSi, where si is the starting time of the i-th job, i = 1,...n. If all jobs have different and non-zero deterioration rates and bi [wzór], where bmin = min{bi}, then an optimal schedule can be found in O(n log n) time. The conducted computational experiments show that the presented algorithm performs very well even on data not satisfying the assumed constraints.

6

Single processor scheduling problems with various models of a due window assignment

Janiak A., Janiak W.A., Marek M.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2009

|

Vol. 57, nr 1

95-101

EN

In the paper we investigate four single processor scheduling problems, which deal with the process of the negotia-tion between a producer and a customer about delivery time of final products. This process is modeled by a due window, which is a generalization of well known classical due date and describes a time interval, in which a job should be finished. Due window assignment is a new approach, which has been investigated in the scientific literature for a few years. In this paper we consider various models of due window assignment. To solve the formu-lated problems we have to find such a schedule of jobs and such an assignment of due windows to each job, which minimizes a given criterion dependent on the maximum or total earliness and tardiness of jobs and due window parameters. One of the main results is the mirror image of the solutions of the considered problems and other problems presented in the scientific literature. The wide survey of the literature is also given.

7

Slack due date assignment and scheduling stochastic jobs on a single machine

Soroush H. M.

Foundations of Computing and Decision Sciences

|

2007

|

Vol. 32, No. 2

153-181

EN

This paper solves the general case of the stochastic single machine scheduling problem where processing times are random variables and due dates are assigned using the slack method. Its objective is to identify the optimal sequence and optimal due dates which minimize the expected total weighted cost of assigning and missing due dates, with no restriction imposed on either cost. The paper presents an exact two-stage algorithm. The first stage (i) utilizes an adjacent precedence relation structure to determine an initial ordering of jobs, (ii) investigates the optimality of the initial job ordering, and (iii) when it cannot prove optimality. it tries to improve the initial ordering by moving jobs from their current positions to any other positions that ensure the precedence relations hold; thus, obtains an incumbent solution. The second stage, which uses the incumbent to show its optimality or search for the optimal solution, is a branch and bound. It utilizes the expected cost of the incumbent as an initial upper bound. It avoids investigating dominated branches by using the job precedence relations; thus, greatly reduces the size of the tree. Extensive computational results show that the incumbent solution obtained in the first stage of the algorithm provides a very tight upper bound cost which fathoms a significant number of non-dominated solutions in the second stage; thus, the proposed algorithm can solve large problems quickly on PC.