Dynamical Artificial Bee Colony for Energy-Efficient Unrelated Parallel Machine Scheduling with Additional Resources and Maintenance

Unrelated parallel machine scheduling problem(UPMSP)is a typical scheduling one and UPMSP with various reallife constraints such as additional resources has been widely studied;however,UPMSP with additional resources,maintenance,and energy-related objectives is seldom investigated.The Artificial Bee Colony(ABC)algorithm has been successfully applied to various production scheduling problems and demonstrates potential search advantages in solving UPMSP with additional resources,among other factors.In this study,an energy-efficient UPMSP with additional resources and maintenance is considered.A dynamical artificial bee colony(DABC)algorithm is presented to minimize makespan and total energy consumption simultaneously.Three heuristics are applied to produce the initial population.Employed bee swarm and onlooker bee swarm are constructed.Computing resources are shifted from the dominated solutions to non-dominated solutions in each swarm when the given condition is met.Dynamical employed bee phase is implemented by computing resource shifting and solution migration.Computing resource shifting and feedback are used to construct dynamical onlooker bee phase.Computational experiments are conducted on 300 instances from the literature and three comparative algorithms and ABC are compared after parameter settings of all algorithms are given.The computational results demonstrate that the new strategies of DABC are effective and that DABC has promising advantages in solving the considered UPMSP.

A Cooperated Imperialist Competitive Algorithm for Unrelated Parallel Batch Machine Scheduling Problem

This study focuses on the scheduling problem of unrelated parallel batch processing machines(BPM)with release times,a scenario derived from the moulding process in a foundry.In this process,a batch is initially formed,placed in a sandbox,and then the sandbox is positioned on a BPM formoulding.The complexity of the scheduling problem increases due to the consideration of BPM capacity and sandbox volume.To minimize the makespan,a new cooperated imperialist competitive algorithm(CICA)is introduced.In CICA,the number of empires is not a parameter,and four empires aremaintained throughout the search process.Two types of assimilations are achieved:The strongest and weakest empires cooperate in their assimilation,while the remaining two empires,having a close normalization total cost,combine in their assimilation.A new form of imperialist competition is proposed to prevent insufficient competition,and the unique features of the problem are effectively utilized.Computational experiments are conducted across several instances,and a significant amount of experimental results show that the newstrategies of CICAare effective,indicating promising advantages for the considered BPMscheduling problems.

Self-adaptive large neighborhood search algorithm for parallel machine scheduling problems

A self-adaptive large neighborhood search method for scheduling n jobs on m non-identical parallel machines with mul- tiple time windows is presented. The problems＇ another feature lies in oversubscription, namely not all jobs can be scheduled within specified scheduling horizons due to the limited machine capacity. The objective is thus to maximize the overall profits of processed jobs while respecting machine constraints. A first-in- first-out heuristic is applied to find an initial solution, and then a large neighborhood search procedure is employed to relax and re- optimize cumbersome solutions. A machine learning mechanism is also introduced to converge on the most efficient neighborhoods for the problem. Extensive computational results are presented based on data from an application involving the daily observation scheduling of a fleet of earth observing satellites. The method rapidly solves most problem instances to optimal or near optimal and shows a robust performance in sensitive analysis.

Rolling optimization algorithm based on collision window for single machine scheduling problem

Focusing on the single machine scheduling problem which minimizes the total completion time in the presence of dynamic job arrivals, a rolling optimization scheduling algorithm is proposed based on the analysis of the character and structure of scheduling. An optimal scheduling strategy in collision window is presented. Performance evaluation of this algorithm is given. Simulation indicates that the proposed algorithm is better than other common heuristic algorithms on both the total performance and stability.

Energy-Performance Tradeoffs in laaS Cloud with Virtual Machine Scheduling

In the cloud data centers,how to map virtual machines(VMs) on physical machines(PMs) to reduce the energy consumption is becoming one of the major issues,and the existing VM scheduling schemes are mostly to reduce energy consumption by optimizing the utilization of physical servers or network elements.However,the aggressive consolidation of these resources may lead to network performance degradation.In view of this,this paper proposes a two-stage VM scheduling scheme:(1) We propose a static VM placement scheme to minimize the number of activating PMs and network elements to reduce the energy consumption;(2) In the premise of minimizing the migration costs,we propose a dynamic VM migration scheme to minimize the maximum link utilization to improve the network performance.This scheme makes a tradeoff between energy efficiency and network performance.We design a new twostage heuristic algorithm for a solution,and the simulations show that our solution achieves good results.

Generalized multiple time windows model based parallel machine scheduling for TDRSS

The scheduling efficiency of the tracking and data relay satellite system（TDRSS）is strictly limited by the scheduling degrees of freedom（DoF）,including time DoF defined by jobs＇ flexible time windows and spatial DoF brought by multiple servable tracking and data relay satellites（TDRSs）.In this paper,ageneralized multiple time windows（GMTW）model is proposed to fully exploit the time and spatial DoF.Then,the improvements of service capability and job-completion probability based on the GMTW are theoretically proved.Further,an asymmetric path-relinking（APR）based heuristic job scheduling framework is presented to maximize the usage of DoF provided by the GMTW.Simulation results show that by using our proposal 11%improvement of average jobcompletion probability can be obtained.Meanwhile,the computing time of the time-to-target can be shorten to 1/9 of the GRASP.

Parallel Machine Scheduling Models with Fuzzy Parameters and Precedence Constraints: A Credibility Approach

A method for modeling the parallel machine scheduling problems with fuzzy parameters and precedence constraints based on credibility measure is provided. For the given n jobs to be processed on m machines, it is assumed that the processing times and the due dates are nonnegative fuzzy numbers and all the weights are positive, crisp numbers. Based on credibility measure, three parallel machine scheduling problems and a goal-programming model are formulated. Feasible schedules are evaluated not only by their objective values but also by the credibility degree of satisfaction with their precedence constraints. The genetic algorithm is utilized to find the best solutions in a short period of time. An illustrative numerical example is also given. Simulation results show that the proposed models are effective, which can deal with the parallel machine scheduling problems with fuzzy parameters and precedence constraints based on credibility measure.

Algorithms for single machine scheduling with availability constraints

It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling problem into a variant of the variable-sized bin packing problem, put forward eight bin packing algorithms adapted from the classic one-dimensional bin packing problem and investigated their performances from both of the worst-case and the average-case scenarios. Analytical results show that the worst-case performance ratios of the algorithms are not less than 2. Experimental results for average cases show that the Best Fit and the Best Fit Decreasing algorithm outperform any others for independent and precedence-constrained jobs respectively.

Minimizing Tardy Jobs in a Single Machine Scheduling Problem with Fuzzy Processing Times and Due Dates

The optimality of a fuzzy logic alternative to the usual treatment of uncertainties in a scheduling system using fuzzy numbers is examined formally. Processing times and due dates are fuzzified and presented by fuzzy numbers. With introducing the necessity measure, we compare fuzzy completion times of jobs with fuzzy due dates to decide whether jobs are tardy. The object is to minimize the numbers of tardy jobs. The efficient solution method for this problem is proposed. And deterministic counterpart of this single machine scheduling problem is a special case of fuzzy version.

An effective estimation of distribution algorithm for parallel litho machine scheduling with reticle constraints

In order to improve the scheduling efficiency of photolithography,bottleneck process of wafer fabrications in the semiconductor industry,an effective estimation of distribution algorithm is proposed for scheduling problems of parallel litho machines with reticle constraints,where multiple reticles are available for each reticle type.First,the scheduling problem domain of parallel litho machines is described with reticle constraints and mathematical programming formulations are put forward with the objective of minimizing total weighted completion time.Second,estimation of distribution algorithm is developed with a decoding scheme specially designed to deal with the reticle constraints.Third,an insert-based local search with the first move strategy is introduced to enhance the local exploitation ability of the algorithm.Finally,simulation experiments and analysis demonstrate the effectiveness of the proposed algorithm.

Identical Machine Scheduling Problem with Sequence-Dependent Setup Times: MILP Formulations Computational Study

This work aims to give a systematic construction of the two families of mixed-integer-linear-programming (MILP) formulations, which are graph- based and sequence-based, of the well-known scheduling problem. Two upper bounds of job completion times are introduced. A numerical test result analysis is conducted with a two-fold objective 1) testing the performance of each solving methods, and 2) identifying and analyzing the tractability of an instance according to the instance structure in terms of the number of machines, of the jobs setup time lengths and of the jobs release date distribution over the scheduling horizon.

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （PART I：EQUAL TIMES AND COSTS）

Abstract Most papers in scheduling research have treated individual job processing times as fixed parameters. However, in many practical situations, a manager may control processing time by reallocating resources. In this paper, authors consider a machine scheduling problem with controllable processing times. In the first part of this paper, a special case where the processing times and compression costs are uniform among jobs is discussed. Theoretical results are derived that aid in developing an O(n 2) algorithm to slove the problem optimally. In the second part of this paper, authors generalize the discussion to general case. An effective heuristic to the general problem will be presented.

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS ： PROOF OF THEOREMS

Abstract This report is virtually the appendix part of the author's previous paper which includes the proofs for the theorems and lemmas.

An approximation algorithm for parallel machine scheduling with simple linear deterioration

In this paper, a parallel machine scheduling problem was considered , where the processing time of a job is a simple linear function of its starting time. The objective is to minimize makespan. A fully polynomial time approximation scheme for the problem of scheduling n deteriorating jobs on two identical machines was worked out. Furthermore, the result was generalized to the case of a fixed number of machines.

Scheduling an Energy-Aware Parallel Machine System with Deteriorating and Learning Effects Considering Multiple Optimization Objectives and Stochastic Processing Time

Currently,energy conservation draws wide attention in industrial manufacturing systems.In recent years,many studies have aimed at saving energy consumption in the process of manufacturing and scheduling is regarded as an effective approach.This paper puts forwards a multi-objective stochastic parallel machine scheduling problem with the consideration of deteriorating and learning effects.In it,the real processing time of jobs is calculated by using their processing speed and normal processing time.To describe this problem in a mathematical way,amultiobjective stochastic programming model aiming at realizing makespan and energy consumption minimization is formulated.Furthermore,we develop a multi-objective multi-verse optimization combined with a stochastic simulation method to deal with it.In this approach,the multi-verse optimization is adopted to find favorable solutions from the huge solution domain,while the stochastic simulation method is employed to assess them.By conducting comparison experiments on test problems,it can be verified that the developed approach has better performance in coping with the considered problem,compared to two classic multi-objective evolutionary algorithms.

Minimizing Total Tardiness in a Two-Machine Flowshop Scheduling Problem with Availability Constraints

In this paper,we consider the problem of minimizing the total tardiness in a deterministic two-machine permutationflowshop scheduling problem subject to release dates of jobs and known unavailability periods of machines.The theoretical and practical importance of minimizing tardiness inflowshop scheduling environment has motivated us to investigate and solve this interested two-machine scheduling problem.Methods that solve this important optimality criterion inflowshop environment are mainly heuristics.In fact,despite the N P-hardnessin the strong sense of the studied problem,to the best of our knowledge there are no approximate algorithms(constructive heuristics or metaheuristics)or an algorithm with worst case behavior bounds proposed to solve this problem.Thus,the design of new promising algorithms is desirable.We developfive metaheuristics for the problem under consideration.These metaheuristics are:the Particle Swarm Optimization(PSO),the Differential Evolution(DE),the Genetic Algorithm(GA),the Ant Colony Optimization(ACO)and the Imperialist Competitive Algorithm(ICA).All the proposed metaheuristics are population-based approaches.These metaheuristics have been improved by integrating different local search procedures in order to provide more satisfactory,especially in term of quality solutions.Computational experiments carried out on a large set of randomly generated instances provide evidence that the Imperialist Competitive Algorithm(ICA)records the best performances.

Machines,Tools and Tool Transporter Concurrent Scheduling in Multi⁃machine FMS with Alternative Routing Using Symbiotic Organisms Search Algorithm

This study explored the concurrent scheduling of machines, tools, and tool transporter(TT) with alternative machines in a multi-machine flexible manufacturing system(FMS), taking into mind the tool transfer durations for minimization of the makespan(MSN). When tools are expensive, just a single copy of every tool kind is made available for use in the FMS system. Because the tools are housed in a central tool magazine(CTM), which then distributes and delivers them to many machines, because there is no longer a need to duplicate the tools in each machine, the associated costs are avoided. Choosing alternative machines for job operations(jb-ons), assigning tools to jb-ons, sequencing jb-ons on machines, and arranging allied trip activities, together with the TT’s loaded trip times and deadheading periods, are all challenges that must be overcome to achieve the goal of minimizing MSN. In addition to a mixed nonlinear integer programming(MNLIP) formulation for this simultaneous scheduling problem, this paper suggests a symbiotic organisms search algorithm(SOSA) for the problem’s solution. This algorithm relies on organisms’ symbiotic interaction strategies to keep living in an ecosystem. The findings demonstrate that SOSA is superior to the Jaya algorithm in providing solutions and that using alternative machines for operations helps bring down MSN.

Optimal online algorithms for scheduling on two identical machines under a grade of service

This work is aimed at investigating the online scheduling problem on two parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels, so each job and machine are labelled with the GoS levels, and each job can be processed by a particular machine only when its GoS level is no less than that of the machine. The goal is to minimize the makespan. For non-preemptive version, we propose an optimal online al-gorithm with competitive ratio 5/3. For preemptive version, we propose an optimal online algorithm with competitive ratio 3/2.

A novel hybrid estimation of distribution algorithm for solving hybrid flowshop scheduling problem with unrelated parallel machine

The hybrid flow shop scheduling problem with unrelated parallel machine is a typical NP-hard combinatorial optimization problem, and it exists widely in chemical, manufacturing and pharmaceutical industry. In this work, a novel mathematic model for the hybrid flow shop scheduling problem with unrelated parallel machine(HFSPUPM) was proposed. Additionally, an effective hybrid estimation of distribution algorithm was proposed to solve the HFSPUPM, taking advantage of the features in the mathematic model. In the optimization algorithm, a new individual representation method was adopted. The(EDA) structure was used for global search while the teaching learning based optimization(TLBO) strategy was used for local search. Based on the structure of the HFSPUPM, this work presents a series of discrete operations. Simulation results show the effectiveness of the proposed hybrid algorithm compared with other algorithms.

Online algorithms for scheduling with machine activation cost on two uniform machines

In this paper we investigate a variant of the scheduling problem on two uniform machines with speeds 1 and s. For this problem, we are given two potential uniform machines to process a sequence of independent jobs. Machines need to be activated before starting to process, and each machine activated incurs a fixed machine activation cost. No machines are initially activated, and when a job is revealed, the algorithm has the option to activate new machines. The objective is to minimize the sum of the makespan and the machine activation cost. We design optimal online algorithms with competitive ratio of (2s+1)/(s+1) for every s≥1.