Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times

A class of nonidentical parallel machine scheduling problems are considered in which the goal is to minimize the total weighted completion time. Models and relaxations are collected. Most of these problems are NP-hard, in the strong sense, or open problems, therefore approximation algorithms are studied. The review reveals that there exist some potential areas worthy of further research.

A new analytical algorithm for computing probability distribution of project completion time

An analytical algorithm was presented for the exact computation of the probability distribution of the project completion time in stochastic networks,where the activity durations are mutually independent and continuously distributed random variables. Firstly,stochastic activity networks were modeled as continuous-time Markov process with a single absorbing state by the well-know method of supplementary variables and the time changed from the initial state to absorbing state is equal to the project completion time.Then,the Markov process was regarded as a special case of Markov skeleton process.By taking advantage of the backward equations of Markov skeleton processes,a backward algorithm was proposed to compute the probability distribution of the project completion time.Finally,a numerical example was solved to demonstrate the performance of the proposed methodology.The results show that the proposed algorithm is capable of computing the exact distribution function of the project completion time,and the expectation and variance are obtained.

Impact of Mobile Access to the Internet on Sales Completion Time in E-Commerce

Supported by a new generation of mobile devices, e-commerce is now in the process of being converted into m-commerce. While the traditional fixed PC access to the Internet continues to be important, the mobile access appears to attract more people because of its flexibility. The purpose of this paper is to develop and analyze a mathematical model for capturing how e-commerce performance would be affected by the mobile access to the Internet, where the original paper by Sumita and Yoshii （2010） is extended for better reality. The traditional e-commerce via the fixed PC access is compared with m-commerce which accommodates both the fixed PC access and the mobile access. The distribution of the number of products purchased by time t and the distribution of the time required for selling K products are derived explicitly. Numerical examples are given for illustrating behavioral differences between m-commerce consumers and traditional e-commerce consumers.

Online Scheduling on Bounded Batch Machines to Minimize the Maximum Weighted Completion Time

We investigate the online scheduling problem on identical parallel-batch machines to minimize the maximum weighted completion time.In this problem,jobs arrive over time and the processing times(of the jobs)are identical,and the batch capacity is bounded.For this problem,we provide a best possible online algorithm with a competitive ratio of(√5+1)/2.Moreover,when restricted to dense-algorithms,we present a best possible dense-algorithm with a competitive ratio of 2.

ON THE COMPLETION TIME AND THE INTERRUPTION TIME OF A JOB PROCESSED ON AN UNRELIABLE MACHINE

This paper considers the completion time and the interruption time of a job processed on an unreliable machine. By using the general theory of stochastic orderings, we obtain the closure properties of the distribution of the completion time and the interruption time on L^+ and PH life distribution classes. We get an exponential bound for the tail probability of the interruption time.

SMART: Speedup Job Completion Time by Scheduling Reduce Tasks

Distributed computing systems have been widely used as the amount of data grows exponentially in the era of information explosion. Job completion time (JCT) is a major metric for assessing their effectiveness. How to reduce the JCT for these systems through reasonable scheduling has become a hot issue in both industry and academia. Data skew is a common phenomenon that can compromise the performance of such distributed computing systems. This paper proposes SMART, which can effectively reduce the JCT through handling the data skew during the reducing phase. SMART predicts the size of reduce tasks based on part of the completed map tasks and then enforces largest-first scheduling in the reducing phase according to the predicted reduce task size. SMART makes minimal modifications to the original Hadoop with only 20 additional lines of code and is readily deployable. The robustness and the effectiveness of SMART have been evaluated with a real-world cluster against a large number of datasets. Experiments show that SMART reduces JCT by up to 6.47%, 9.26%, and 13.66% for Terasort, WordCount and InvertedIndex respectively with the Purdue MapReduce benchmarks suite (PUMA) dataset.

Partitioning of Independent Tasks for Minimizing Completion Time and Total Waiting Time

Parallel processors provide fast computing environments for various users.But the real efficiencies ofparallel processors intensively depend on the partitioning strategies of tasks over the processors.In thispaper,the partitioning problems of independent tasks for homogeneous system of parallel processors arequantitatively studied.We adopt two criteria,minimizing the completion time and the total waiting time,to determine the optimal partitioning strategy.

ON THE COMPLETION TIME OF A JOB PROCESSED ON AN UNRELIABLE MACHINE

In this paper, we consider the completion time of a job processed on an unreliable machine. Assume that the lifetime and the repair time of the machine and the service time of the job have general distributions. We obtain the Laplace-Stieltjes transforms and the expectations of the distributions of the completion time, the interruption time and the actual service time. Under some special cases, we derive sufficient and necessary (or sufficient) conditions such that the completion time is larger and smaller than the service time in the sense of the Laplace transform order (or the expectation), respectively

An Improved Harris Hawk Optimization Algorithm for Flexible Job Shop Scheduling Problem

Flexible job shop scheduling problem(FJSP)is the core decision-making problem of intelligent manufacturing production management.The Harris hawk optimization(HHO)algorithm,as a typical metaheuristic algorithm,has been widely employed to solve scheduling problems.However,HHO suffers from premature convergence when solving NP-hard problems.Therefore,this paper proposes an improved HHO algorithm(GNHHO)to solve the FJSP.GNHHO introduces an elitism strategy,a chaotic mechanism,a nonlinear escaping energy update strategy,and a Gaussian random walk strategy to prevent premature convergence.A flexible job shop scheduling model is constructed,and the static and dynamic FJSP is investigated to minimize the makespan.This paper chooses a two-segment encoding mode based on the job and the machine of the FJSP.To verify the effectiveness of GNHHO,this study tests it in 23 benchmark functions,10 standard job shop scheduling problems(JSPs),and 5 standard FJSPs.Besides,this study collects data from an agricultural company and uses the GNHHO algorithm to optimize the company’s FJSP.The optimized scheduling scheme demonstrates significant improvements in makespan,with an advancement of 28.16%for static scheduling and 35.63%for dynamic scheduling.Moreover,it achieves an average increase of 21.50%in the on-time order delivery rate.The results demonstrate that the performance of the GNHHO algorithm in solving FJSP is superior to some existing algorithms.

A Linear Programming Approach for Parallel Cell Scheduling with Sequence-Dependent Setup Times

In this study, we consider the problem of scheduling a set of jobs with sequence-dependent setup times on a set of parallel production cells. The objective of this study is to minimize the total completion time. We note that total customer demands for each type should be satisfied, and total required production time in each cell cannot exceed the capacity of the cell. This problem is formulated as an integer programming model and an interface is designed to provide integrity between data and software. Mathematical model is tested by both randomly generated data set and real-world data set from a factory that produce automotive components. As a result of this study, the solution which gives the best alternative production schedule is obtained.

SIMULATED ANNEALING BASED POLYNOMIAL TIME QOS ROUTING ALGORITHM FOR MANETS

Multi-constrained Quality-of-Service (QoS) routing is a big challenge for Mobile Ad hoc Networks (MANETs) where the topology may change constantly. In this paper a novel QoS Routing Algorithm based on Simulated Annealing (SA_RA) is proposed. This algorithm first uses an energy function to translate multiple QoS weights into a single mixed metric and then seeks to find a feasible path by simulated annealing. The pa- per outlines simulated annealing algorithm and analyzes the problems met when we apply it to Qos Routing (QoSR) in MANETs. Theoretical analysis and experiment results demonstrate that the proposed method is an effective approximation algorithms showing better performance than the other pertinent algorithm in seeking the (approximate) optimal configuration within a period of polynomial time.

Gorilla Troops Optimizer Based Fault Tolerant Aware Scheduling Scheme for Cloud Environment

In cloud computing(CC),resources are allocated and offered to the cli-ents transparently in an on-demand way.Failures can happen in CC environment and the cloud resources are adaptable tofluctuations in the performance delivery.Task execution failure becomes common in the CC environment.Therefore,fault-tolerant scheduling techniques in CC environment are essential for handling performance differences,resourcefluxes,and failures.Recently,several intelli-gent scheduling approaches have been developed for scheduling tasks in CC with no consideration of fault tolerant characteristics.With this motivation,this study focuses on the design of Gorilla Troops Optimizer Based Fault Tolerant Aware Scheduling Scheme(GTO-FTASS)in CC environment.The proposed GTO-FTASS model aims to schedule the tasks and allocate resources by considering fault tolerance into account.The GTO-FTASS algorithm is based on the social intelligence nature of gorilla troops.Besides,the GTO-FTASS model derives afitness function involving two parameters such as expected time of completion(ETC)and failure probability of executing a task.In addition,the presented fault detector can trace the failed tasks or VMs and then schedule heal submodule in sequence with a remedial or retrieval scheduling model.The experimental vali-dation of the GTO-FTASS model has been performed and the results are inspected under several aspects.Extensive comparative analysis reported the better outcomes of the GTO-FTASS model over the recent approaches.

Scheduling Step-Deteriorating Jobs on Parallel Machines by Mixed Integer Programming

Production scheduling has a major impact on the productivity of the manufacturing process. Recently, scheduling problems with deteriorating jobs have attracted increasing attentions from researchers. In many practical situations,it is found that some jobs fail to be processed prior to the pre-specified thresholds,and they often consume extra deteriorating time for successful accomplishment. Their processing times can be characterized by a step-wise function. Such kinds of jobs are called step-deteriorating jobs. In this paper,parallel machine scheduling problem with stepdeteriorating jobs( PMSD) is considered. Due to its intractability,four different mixed integer programming( MIP) models are formulated for solving the problem under consideration. The study aims to investigate the performance of these models and find promising optimization formulation to solve the largest possible problem instances. The proposed four models are solved by commercial software CPLEX. Moreover,the near-optimal solutions can be obtained by black-box local-search solver LocalS olver with the fourth one. The computational results show that the efficiencies of different MIP models depend on the distribution intervals of deteriorating thresholds, and the performance of LocalS olver is clearly better than that of CPLEX in terms of the quality of the solutions and the computational time.

Optimal Resource Allocation and Quality of Service Prediction in Cloud

In the present scenario,cloud computing service provides on-request access to a collection of resources available in remote system that can be shared by numerous clients.Resources are in self-administration;consequently,clients can adjust their usage according to their requirements.Resource usage is estimated and clients can pay according to their utilization.In literature,the existing method describes the usage of various hardware assets.Quality of Service(QoS)needs to be considered for ascertaining the schedule and the access of resources.Adhering with the security arrangement,any additional code is forbidden to ensure the usage of resources complying with QoS.Thus,all monitoring must be done from the hypervisor.To overcome the issues,Robust Resource Allocation and Utilization(RRAU)approach is developed for optimizing the management of its cloud resources.The work hosts a numerous virtual assets which could be expected under the circumstances and it enforces a controlled degree of QoS.The asset assignment calculation is heuristic,which is based on experimental evaluations,RRAU approach with J48 prediction model reduces Job Completion Time(JCT)by 4.75 s,Make Span(MS)6.25,and Monetary Cost(MC)4.25 for 15,25,35 and 45 resources are compared to the conventional methodologies in cloud environment.

Optimizing the Resource Utilization of Datacenter Networks with OpenFlow

Decreasing the flow completion time(FCT) and increasing the throughput are two fundamental targets in datacenter networks(DCNs), but current mechanisms mostly focus on one of the problems. In this paper, we propose OFMPC, an Open Flow based Multi Path Cooperation framework, to decrease FCT and increase the network throughput. OFMPC partitions the end-to-end transmission paths into two classes, which are low delay paths(LDPs) and high throughput paths(HTPs), respectively. Short flows are assigned to LDPs to avoid long queueing delay, while long flows are assigned to HTPs to guarantee their throughput. Meanwhile, a dynamic scheduling mechanism is presented to improve network efficiency. We evaluate OFMPC in Mininet emulator and a testbed, and the experimental results show that OFMPC can effectively decrease FCT. Besides, OFMPC also increases the throughput up to more than 84% of bisection bandwidth.

Research on the Trusted Energy-Saving Transmission of Data Center Network

According to the high operating costs and a large number of energy waste in the current data center network architectures, we propose a kind of trusted flow preemption scheduling combining the energy-saving routing mechanism based on typical data center network architecture. The mechanism can make the network flow in its exclusive network link bandwidth and transmission path, which can improve the link utilization and the use of the network energy efficiency. Meanwhile, we apply trusted computing to guarantee the high security, high performance and high fault-tolerant routing forwarding service, which helps improving the average completion time of network flow.

Optimal Batching Structures of Single Machine Scheduling

A batch is a subset of jobs which must be processed jointly in either serial or parallel form. For the single machine, batching, total completion time scheduling problems, the algorithmic aspects have been extensively studied in the literature. This paper presents the optimal hatching structures of the problems on the batching ways： all jobs in exactly N（arbitrary fix batch number and 1 〈 N 〈 n） batches.

Mathematical Modeling and a Multiswarm Collaborative Optimization Algorithm for Fuzzy Integrated Process Planning and Scheduling Problem

Considering both process planning and shop scheduling in manufacturing can fully utilize their complementarities,resulting in improved rationality of process routes and high-quality and efficient production. Hence,the study of Integrated Process Planning and Scheduling (IPPS) has become a hot topic in the current production field. However,when performing this integrated optimization,the uncertainty of processing time is a realistic key point that cannot be neglected. Thus,this paper investigates a Fuzzy IPPS (FIPPS) problem to minimize the maximum fuzzy completion time. Compared with the conventional IPPS problem,FIPPS considers the fuzzy process time in the uncertain production environment,which is more practical and realistic. However,it is difficult to solve the FIPPS problem due to the complicated fuzzy calculating rules. To solve this problem,this paper formulates a novel fuzzy mathematical model based on the process network graph and proposes a MultiSwarm Collaborative Optimization Algorithm (MSCOA) with an integrated encoding method to improve the optimization. Different swarms evolve in various directions and collaborate in a certain number of iterations. Moreover,the critical path searching method is introduced according to the triangular fuzzy number,allowing for the calculation of rules to enhance the local searching ability of MSCOA. The numerical experiments extended from the well-known Kim benchmark are conducted to test the performance of the proposed MSCOA. Compared with other competitive algorithms,the results obtained by MSCOA show significant advantages,thus proving its effectiveness in solving the FIPPS problem.

Predictive-reactive Strategy for Flowshop Rescheduling Problem:Minimizing the Total Weighted Waiting Times and Instability

Due to the fourth revolution experiencing,referred to as Industry 4.0,many production firms are devoted to integrating new technological tools to their manufacturing process.One of them,is rescheduling the tasks on the machines responding to disruptions.While,for static scheduling,the efficiency criteria measure the performance of scheduling systems,in dynamic environments,the stability criteria are also used to assess the impact of jobs deviation.In this paper,a new performance measure is investigated for a flowshop rescheduling problem.This one considers simultaneously the total weighted waiting time as the efficiency criterion,and the total weighted completion time deviation as the stability criterion.This fusion could be a very helpful and significant measure for real life industrial systems.Two disruption types are considered:jobs arrival and jobs cancellation.Thus,a Mixed Integer Linear Programming(MILP)model is developed,as well as an iterative predictive-reactive strategy for dealing with the online part.At last,two heuristic methods are proposed and discussed,in terms of solution quality and computing time.

Prognostic factors of non-infarct-related arterial revascularization in STEMI patients with multivessel disease

Background Multivessel disease(MVD)is common in patients presenting with ST-segment elevation myocardial infarction(STEMI).But there is controversy over how to manage significant lesions in non-infarct-related artery(non-IRA).Methods A total of 221 patients diagnosed with STEMI and MVD who underwent percutaneous coronary intervention(PCI)at our cardiology department between January 2018 and June 2021 were included in this study.Among them,115 patients underwent complete revascularization within 30 days and were assigned to the complete revascularization group,while 106 patients who did not undergo complete revascularization within 30 days were assigned to the IRA-only revascularization group.Patients were followed up at 12 months.The primary endpoint event was adverse cardiovascular events(MACEs).Results There was no significant statistical difference in MACEs between the two groups of patients,but the incidence of heart failure in the IRA-Only group was significantly higher than that in the complete revascularization group.In the complete revascularization group,the number of stents,Killip class Ⅱ/Ⅲ on admission,and complete revascularization time were independent predictors of MACEs.Receiver operating characteristic curve(ROC)curve analysis showed that complete revascularization time had good predictive power for MACEs(Area under the curve:0.74695%CI:0.680-0.801),with a cut-off value of 10.3 days.Conclusions For STEMI patients with concurrent MVD,complete revascularization can reduce the incidence of heart failure.What's more,short-term staged(within 10 days)complete revascularization may further improve clinical outcomes.