On-line Scheduling Algorithm for Penicillin Fed-batch Fermentation

An on-line scheduling algorithm to maximize gross profit of penicillin fed-batch fermentation is proposed. According to the on-line classification method, fed-batch fermentation batches are classified into three categories. Using the scheduling strategy, the optimal termination sequence of batches is obtained. Pseudo on-line simulations for testing the proposed algorithm with the data from industrial scale penicillin fermentation are carried out.

Semi on-line scheduling for maximizing the minimum machine completion time on three uniform machines

The paper investigates a semi on-line scheduling problem wherein the largest processing time of jobs done by three uniform machines M1, M2, M3 is known in advance. A speed si (s1=1, s2=r, s3=s, 1≤r≤s) is associated with machine Mi. Our goal is to maximize Cmin?the minimum workload of the three machines. We present a min3 algorithm and prove its competitive ratio is max{r+1,(3s+r+1)/(1+r+s)}, with the lower bound being at least max{2,r}. We also claim the competitive ratio of min3 algo- rithm cannot be improved and is the best possible for 1≤s≤2, r=1.

Semi On-line Scheduling Problem for Maximizing the Minimum Machine Completion Time on mIdentical Machines

In this paper, a semi on-line version on m ide ntical machines M 1, M 2, …,M m(m≥3) was considered, where th e processing time of the largest job is known in advance. Our goal is to maximiz e the minimum machine load, an NPLS algorithm was presented and its worst-case ratio was proved to be equal to m-1 which is the best possible value. It is concluded that if the total processing time of jobs is also known to be greater than (2m-1)p max where p max is the largest job' s processing time, then the worst-case ratio is 2-1/m.

On-Line Scheduling for Jobs with Arbitrary Release Times on Parallel Related Uniform Machines

A parallel related uniform machine system consists of m machines with different processing speeds. The speed of any machine is independent on jobs. In this paper, we consider online scheduling for jobs with arbitrary release times on the parallel uniform machine system. The jobs appear over list in terms of order. An order includes the processing size and releasing time of a job. For this model, an algorithm with competitive ratio of 12 is addressed in this paper.

Hierarchical On-line Scheduling of Multiproduct Batch Plants with a Combined Approach of Mathematical Programming and Genetic Algorithm

In this contribution we present an online scheduling algorithm for a real world multiproduct batch plant. The overall mixed integer nonlinear programming (MINLP) problem is hierarchically structured into a mixed integer linear programming (MILP) problem first and then a reduced dimensional MINLP problem, which are optimized by mathematical programming (MP) and genetic algorithm (GA) respectively. The basis idea relies on combining MP with GA to exploit their complementary capacity. The key features of the hierarchical model are explained and illustrated with some real world cases from the multiproduct batch plants.

Ordinal Semi On-Line Scheduling for Jobs with Arbitrary Release Times on Identical Parallel Machines

In this paper, we investigate the problem of semi-on-line scheduling n jobs on m identical parallel machines under the assumption that the ordering of the jobs by processing time is known and the jobs have arbitrary release times. Our aim is to minimize the maximum completion time. An ordinal algorithm is investigated and its worst case ratio is analyzed.

Better Algorithm for Order On-Line Scheduling on Uniform Machines

In this paper, we consider online scheduling for jobs with arbitrary release times on the parallel uniform machine system. An algorithm with competitive ratio of 7.4641 is addressed, which is better than the best existing result of 12.

ON-LINE SCHEDULING OF UNIT TIME JOBS WITH REJECTION ON UNIFORM MACHINES

The authors consider the problem of on-line scheduling of unit execution time jobs on uniform machines with rejection penalty. The jobs arrive one by one and can be either accepted and scheduled, or be rejected. The objective is to minimize the total completion time of the accepted jobs and the total penalty of the rejection jobs. The authors propose an on-line algorithm and prove that the competitive ratio is 1/2 （2 W √3） ≈ 1.86602.

SEMI ON-LINE SCHEDULING PROBLEM FOR MAXIMIZING THE MINIMUM MACHINE COMPLETION TIME ON TWO UNIFORM MACHINES

Ia this paper, we consider a semi on-line version on two uniform machines Mi, i = 1, 2, where the processing time of the largest job is known in advance. A speed si（s1 = 1, 1 ≤s2 = s） is associated with machine Mi. Our goal is to maximize the Cmin. We give a Cmin 2 algorithm and prove its competitive ratio is at most 2s＋1/s＋1 We also claim the Cmin 2 algorithm is tight and the gap between the competitive ratio of Cmin2 algorithm and the optimal value is not greater than 0.555. It is obvious that our result coincides with that given by He for s =1.

On-Line Scheduling on Parallel Machines to Minimize the Makespan

This paper considers two parallel machine scheduling problems, where the objectives of both problems are to minimize the makespan, and the jobs arrive over time, on two uniform machines with speeds 1 and s （s 〉 1）, and on m identical machines, respectively. For the first problem, the authors show that the on-line LPT algorithm has a competitive ratio of （1 ＋ √5）/2 ≈ 1.6180 and the bound is tight. Furthermore, the authors prove that the on-line LPT algorithm has the best possible competitive ratio if s ≥ 1.8020. For the second problem, the authors present a lower bound of （15 - √17）/8 ≈ 1.3596 on the competitive ratio of any deterministic on-line algorithm. This improves a previous result of 1.3473.

Randomized On-Line Scheduling Similar Jobs to Minimize Makespan on Two Identical Processors

In this paper we consider an on-line scheduling problem, where jobs with similar processing times within [1, r] arrive one by one to be scheduled in an on-line setting on two identical parallel processors without preemption. The objective is to nlinimize makespan. We devise a randomized on-line algorithm for this problem along with a lower bound.

ON-LINE SCHEDULING WITH REJECTION ON IDENTICAL PARALLEL MACHINES

In this paper, we consider the on-line scheduling of unit time jobs with rejection on rn identical parallel machines. The objective is to minimize the total completion time of the accepted jobs plus the total penalty of the rejected jobs. We give an on-line algorithm for the problem with competitive ratio 1/2 （2 ＋√3） ≈ 1.86602.

Algorithms for semi on-line multiprocessor scheduling problems

In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off\|line or on\|line environment. But in practice, problems are often not really off\|line or on\|line but somehow in between. This means that, with respect to the on\|line problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi on\|line ones. The authors studied two semi on\|line multiprocessor scheduling problems, in which, the total processing time of all tasks is known in advance, or all processing times lie in a given interval. They proposed approximation algorithms for minimizing the makespan and analyzed their performance guarantee. The algorithms improve the known results for 3 or more processor cases in the literature.

Single Machine Scheduling with Time-Dependent Learning Effect and Non-Linear Past-Sequence-Dependent Setup Times

This paper studies a single machine scheduling problem with time-dependent learning and setup times. Time-dependent learning means that the actual processing time of a job is a function of the sum of the normal processing times of the jobs already scheduled. The setup time of a job is proportional to the length of the already processed jobs, that is, past-sequence-dependent (psd) setup time. We show that the addressed problem remains polynomially solvable for the objectives, i.e., minimization of the total completion time and minimization of the total weighted completion time. We also show that the smallest processing time (SPT) rule provides the optimum sequence for the addressed problem.

A Review of On-Line Machine Scheduling:Algorithms and Competitiveness

在过去的十年里，在线算法的研究吸引了广泛的兴趣．本文对在排序和时间表问题中的各种有效的在线算法以及它们的竞争度作一综述．

AN ON-LINE SCHEDULING PROBLEM OF PARALLEL MACHINES WITH COMMON MAINTENANCE TIME

In this paper, the authors consider an on-line scheduling problem of rn （m≥ 3） identical machines with common maintenance time interval and nonresumable availability. For the case that the length of maintenance time interval is larger than the largest processing time of jobs, the authors prove that any on-line algorithm has not a constant competitive ratio. For the case that the length of maintenance time interval is less than or equal to the largest processing time of jobs, the authors prove a lower bound of 3 on the competitive ratio. The authors give an on-line algorithm with competitive 1 ratio 4 - 1/m. In particular, for the case of m = 3, the authors prove the competitive ratio of the on-line algorithm is 10/3.

SEMI-ON-LINE SCHEDULING PROBLEMS FOR MAXIMIZING THE MINIMUM MACHINE COMPLETION TIME

This paper investigates several different semi-on-line two-machine scheduling problems for maximizing the minimum machine completion time. For each problem, we propose a best possible algorithm.

MCWOA Scheduler:Modified Chimp-Whale Optimization Algorithm for Task Scheduling in Cloud Computing

Cloud computing provides a diverse and adaptable resource pool over the internet,allowing users to tap into various resources as needed.It has been seen as a robust solution to relevant challenges.A significant delay can hamper the performance of IoT-enabled cloud platforms.However,efficient task scheduling can lower the cloud infrastructure’s energy consumption,thus maximizing the service provider’s revenue by decreasing user job processing times.The proposed Modified Chimp-Whale Optimization Algorithm called Modified Chimp-Whale Optimization Algorithm(MCWOA),combines elements of the Chimp Optimization Algorithm(COA)and the Whale Optimization Algorithm(WOA).To enhance MCWOA’s identification precision,the Sobol sequence is used in the population initialization phase,ensuring an even distribution of the population across the solution space.Moreover,the traditional MCWOA’s local search capabilities are augmented by incorporating the whale optimization algorithm’s bubble-net hunting and random search mechanisms into MCWOA’s position-updating process.This study demonstrates the effectiveness of the proposed approach using a two-story rigid frame and a simply supported beam model.Simulated outcomes reveal that the new method outperforms the original MCWOA,especially in multi-damage detection scenarios.MCWOA excels in avoiding false positives and enhancing computational speed,making it an optimal choice for structural damage detection.The efficiency of the proposed MCWOA is assessed against metrics such as energy usage,computational expense,task duration,and delay.The simulated data indicates that the new MCWOA outpaces other methods across all metrics.The study also references the Whale Optimization Algorithm(WOA),Chimp Algorithm(CA),Ant Lion Optimizer(ALO),Genetic Algorithm(GA)and Grey Wolf Optimizer(GWO).

DR-IS:Dynamic Response Incremental Scheduling in Time-Sensitive Network

Time-Sensitive Network(TSN)with deterministic transmission capability is increasingly used in many emerging fields.It mainly guarantees the Quality of Service(QoS)of applications with strict requirements on time and security.One of the core features of TSN is traffic scheduling with bounded low delay in the network.However,traffic scheduling schemes in TSN are usually synthesized offline and lack dynamism.To implement incremental scheduling of newly arrived traffic in TSN,we propose a Dynamic Response Incremental Scheduling(DR-IS)method for time-sensitive traffic and deploy it on a software-defined time-sensitive network architecture.Under the premise of meeting the traffic scheduling requirements,we adopt two modes,traffic shift and traffic exchange,to dynamically adjust the time slot injection position of the traffic in the original scheme,and determine the sending offset time of the new timesensitive traffic to minimize the global traffic transmission jitter.The evaluation results show that DRIS method can effectively control the large increase of traffic transmission jitter in incremental scheduling without affecting the transmission delay,thus realizing the dynamic incremental scheduling of time-sensitive traffic in TSN.

STRONGLY CONVERGENT INERTIAL FORWARD-BACKWARD-FORWARD ALGORITHM WITHOUT ON-LINE RULE FOR VARIATIONAL INEQUALITIES

This paper studies a strongly convergent inertial forward-backward-forward algorithm for the variational inequality problem in Hilbert spaces.In our convergence analysis,we do not assume the on-line rule of the inertial parameters and the iterates,which have been assumed by several authors whenever a strongly convergent algorithm with an inertial extrapolation step is proposed for a variational inequality problem.Consequently,our proof arguments are different from what is obtainable in the relevant literature.Finally,we give numerical tests to confirm the theoretical analysis and show that our proposed algorithm is superior to related ones in the literature.