Online MapReduce scheduling problem of minimizing the makespan

MapReduce system is a popular big data processing framework, and the performance of it is closely related to the efficiency of the centralized scheduler. In practice, the centralized scheduler often has little information in advance, which means each job may be known only after being released. In this paper, hence, we consider the online MapReduce scheduling problem of minimizing the makespan, where jobs are released over time. Both preemptive and non-preemptive version of the problem are considered. In addition, we assume that reduce tasks cannot be parallelized because they are often complex and hard to be decomposed. For the non-preemptive version, we prove the lower bound is \(\frac{m+m(\Psi (m)-\Psi (k))}{k+m(\Psi (m)-\Psi (k))}\), higher than the basic online machine scheduling problem, where k is the root of the equation \(k=\big \lfloor {\frac{m-k}{1+\Psi (m)-\Psi (k)}+1 }\big \rfloor \) and m is the quantity of machines. Then we devise an \((2-\frac{1}{m})\)-competitive online algorithm called MF-LPT (Map First-Longest Processing Time) based on the LPT. For the preemptive version, we present a 1-competitive algorithm for two machines.     

An FPTAS for uniform machine scheduling to minimize makespan with linear deterioration

This paper consider m uniform (parallel) machine scheduling with linear deterioration to minimize the makespan. In an uniform machine environment, all machines have different processing speeds. Linear deterioration means that job’s actual processing time is a linear increasing function on its execution starting time. We propose a fully polynomial-time approximation scheme (FPTAS) to show the problem is NP-hard in the ordinary sense.     

Effective heuristics for the blocking flowshop scheduling problem with makespan minimization

The blocking flowshop scheduling problem with makespan criterion has important applications in a variety of industrial systems. Heuristics that explore specific characteristics of the problem are essential for many practical systems to find good solutions with limited computational effort. This paper first presents two simple constructive heuristics, namely weighted profile fitting (wPF) and PW, based on the profile fitting (PF) approach of McCormick et al. [Sequencing in an assembly line with blocking to minimize cycle time. Operations Research 1989;37:925-36] and the characteristics of the problem. Then, three improved constructive heuristics, called PF-NEH, wPF-NEH, and PW-NEH, are proposed by combining the PF, wPF, and PW with the enumeration procedure of the Nawaz-Enscore-Ham (NEH) heuristic [A heuristic algorithm for the m-machine, n-job flow shop sequencing problem. OMEGA-International Journal of Management Science 1983;11:91-5] in an effective way. Thirdly, three composite heuristics i.e., PF-NEH_LS, wPF-NEH_LS, and PW-NEH_LS, are developed by using the insertion-based local search method to improve the solutions generated by the constructive heuristics. Computational simulations and comparisons are carried out based on the well-known flowshop benchmarks of Taillard [Benchmarks for basic scheduling problems. European Journal of Operation Research 1993;64:278-85] that are considered as blocking flowshop instances. The results show that the presented constructive heuristics perform significantly better than the existing ones, and the proposed composite heuristics further improve the presented constructive heuristics by a considerable margin. In addition, 17 new best-known solutions for Taillard benchmarks with large scale are found by the presented heuristics.     

Online tradeoff scheduling on a single machine to minimize makespan and maximum lateness

In this paper, we consider the following single machine online tradeoff scheduling problem. A set of n independent jobs arrive online over time. Each job \(J_{j}\) has a release date \(r_{j}\), a processing time \(p_{j}\) and a delivery time \(q_{j}\). The characteristics of a job are unknown until it arrives. The goal is to find a schedule that minimizes the makespan \(C_{\max } = \max _{1 \le j \le n} C_{j}\) and the maximum lateness \(L_{\max } = \max _{1 \le j \le n} L_{j}\), where \(L_{j} = C_{j} + q_{j}\). For the problem, we present a nondominated \(( \rho , 1 + \displaystyle \frac{1}{\rho } )\)-competitive online algorithm for each \(\rho \) with \( 1 \le \rho \le \displaystyle \frac{\sqrt{5} + 1}{2}\).     

Asymptotically optimal policy for stochastic job shop scheduling problem to minimize makespan

This paper studies the large-scale stochastic job shop scheduling problem with general number of similar jobs, where the processing times of the same step are independently drawn from a known probability distribution, and the objective is to minimize the makespan. For the stochastic problem, we introduce the fluid relaxation of its deterministic counterpart, and define a fluid schedule for the fluid relaxation. By tracking the fluid schedule, a policy is proposed for the stochastic job shop scheduling problem. The expected value of the gap between the solution produced by the policy and the optimal solution is proved to be O(1), which indicates the policy is asymptotically optimal in expectation.     

Scheduling tool changes and special jobs on a single machine to minimize makespan

This paper considers a variation of the classical single machine scheduling problem with tool changes. In the variation, two sets of jobs, namely special jobs and normal jobs, are considered. By special jobs, we mean that each special job must be processed within the first prefixed time units of a tool life. To solve the scheduling problem with small size and moderate size, we propose two mathematical programming models. To solve the scheduling problem with large size, we propose three sets of algorithms and focus on the performance of six algorithms based on the studies of a new bin packing problem. Worst-case analysis is conducted. Numerical experiment shows that each of the six algorithms can solve instances with up to 5000 jobs in about 0.5 s with an average relative error less than 4%.     

A note on a makespan minimization problem with a multi-ability learning effect

In the scheduling literature the learning effect is perceived as a process of acquiring experience by a processor (e.g. a human worker) in one ability. However, in many real-life problems the processor, during execution of jobs, increases its experience in different, very often independent, abilities (skills). In consequence, it causes the overall growth of the efficiency of the processor. According to this observation, in this paper, we bring into scheduling a new approach called multi-ability learning that generalizes the existing ones and models more precisely real-life settings. On this basis, we focus on a makespan minimization problem with the proposed learning model and provide optimal polynomial time algorithms for its special cases, which often occur in management.     

Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan

We study the online scheduling problem on m identical parallel machines to minimize makespan, i.e., the maximum completion time of the jobs, where m is given in advance and the jobs arrive online over time. We assume that the jobs, which arrive at some nonnegative real times, are of equal-length and are restricted by chain precedence constraints. Moreover, the jobs arriving at distinct times are independent, and so, only the jobs arriving at a common time are restricted by the chain precedence constraints. In the literature, a best possible online algorithm of a competitive ratio 1.3028 is given for the case \(m=2\). But the problem is unaddressed for \(m\ge 3\). In this paper, we present a best possible online algorithm for the problem with \(m\ge 3\), where the algorithm has a competitive ratio of 1.3028 for \(3\le m\le 5\) and 1.3146 for \(m\ge 6\).     

A pairwise interchange algorithm for parallel machine scheduling

This paper considers the problem of non-preemptive scheduling n tasks on m identical parallel processors to minimize makespan for simultaneous arrivals. Based on a pairwise interchange method, an efficient algorithm ispresented which is able to give a near-optimal schedule in a short time through suitable pairwise interchange between tasks, after an initial solution is constructed. The behaviour of the algorithm is discussed. Testing results prove its high performance in comparison with available simple heuristic procedures. Finally, the algorithm is generalized for the problems of non-identical processors and non-simultaneous arrivals.     

一种差异工件单机批调度问题的蚁群优化算法

由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的.从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了JACO(ant colony optimization based a job sequence)和BACO(ant colony optimization based a batch sequence)两种蚁群优化算法.在算法JACO中,解的编码为工件序列,它对应着用BF(best fit)分批规则生成的调度方案,信息素代表工件间的排列顺序;在算法BACO中,解的编码为批序列,信息素代表工件间的批相关性,由此信息素通过中间信息素量来构造相应的解,并引入特定的局部优化策略,提高了算法的搜索效率.实验表明,与以往文献中的SA(simula-ted annealing)、GA(genetic algorithm)算法以及FFLPT(first-fit longest processing time)、BFLPT (best-fit longest processing time)启发式规则相比,算法JACO和BACO明显优于它们,且BACO算法比JACO算法效果更好.     

Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence

In this paper, we introduce the concept of “workload fence" into online machine rental and machine scheduling problems. With the knowledge of workload fence, online algorithms acquire the information of a finite number of first released jobs in advance. The concept originates from the frozen time fence in the domain of master scheduling in materials management. The total processing time of the jobs foreseen, corresponding to a finite number of jobs, is called workload fence, which is irrelevant to the job sequence. The remaining jobs in the sequence, however, can only become known on their arrival. This work aims to reveal whether the knowledge of workload fence helps to boost the competitive performance of deterministic online algorithms. For the online machine rental problem, we prove that the competitiveness of online algorithms can be improved with a sufficiently large workload fence. We further propose a best online algorithm for the corresponding scenario. For online parallel machine scheduling with workload fence, we give a positive answer to the above question for the case where the workload fence is equal to the length of the longest job. We also show that the competitiveness of online algorithms may not be improved even with a workload fence strictly larger than the largest length of a job. The results help one manager to make a better decision regarding the tradeoff between the performance improvement of online algorithms and the cost caused to acquire the knowledge of workload fence.

     

A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation

The hybrid flowshop scheduling (HFS) problem with the objective of minimising the makespan has important applications in a variety of industrial systems. This paper presents an effective discrete artificial bee colony (DABC) algorithm that has a hybrid representation and a combination of forward decoding and backward decoding methods for solving the problem. Based on the dispatching rules, the well-known NEH heuristic, and the two decoding methods, we first provide a total of 24 heuristics. Next, an initial population is generated with a high level of quality and diversity based on the presented heuristics. A new control parameter is introduced to conduct the search of employed bees and onlooker bees with the intention of balancing the global exploration and local exploitation, and an enhanced strategy is proposed for the scout bee phase to prevent the algorithm from searching in poor regions of the solution space. A problem-specific local refinement procedure is developed to search for solution space that is unexplored by the honey bees. Afterward, the parameters and operators of the proposed DABC are calibrated by means of a design of experiments approach. Finally, a comparative evaluation is conducted, with the best performing algorithms presented for the HFS problem under consideration, and with adaptations of some state-of-the-art metaheuristics that were originally designed for other HFS problems. The results show that the proposed DABC performs much better than the other algorithms in solving the HFS problem with the makespan criterion.     

A memetic differential evolution algorithm for energy-efficient parallel machine scheduling

This paper considers an energy-efficient bi-objective unrelated parallel machine scheduling problem to minimize both makespan and total energy consumption. The parallel machines are speed-scaling. To solve the problem, we propose a memetic differential evolution (MDE) algorithm. Since the problem involves assigning jobs to machines and selecting an appropriate processing speed level for each job, we characterize each individual by two vectors: a job-machine assignment vector and a speed vector. To accelerate the convergence of the algorithm, only the speed vector of each individual evolves and a list scheduling heuristic is applied to derive its job-machine assignment vector based on its speed vector. To further enhance the algorithm, we propose efficient speed adjusting and job-machine swap heuristics and integrate them into the algorithm as a local search approach by an adaptive meta-Lamarckian learning strategy. Computational results reveal that the incorporation of list scheduling heuristic and local search greatly strengthens the algorithm. Computational experiments also show that the proposed MDE algorithm outperforms SPEA-II and NSGA-II significantly.     

Scheduling of unrelated parallel machines when machine availability is specified

Scheduling problems typically assume uninterrupted availability of machines such that jobs can be processed at any time during this uninterrupted period. However, this assumption is seldom valid in reality. For a variety of reasons, e.g. machine adjustments, shift changes, planned maintenance, etc. machines are available only at specified times. The duration for which the machine is not available is known as the vacation. This paper considers the problem of scheduling jobs on unrelated parallel machines when machine vacations are specified. Two cases are considered, first, when the machine vacations are known apriori, and the second, when these constraints are not known apriori. Algorithms have been developed for both models, and computational results are also reported.     

Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval

In this article, we consider the non-resumable case of the single machine scheduling problem with a fixed non-availability interval. We aim to minimize the makespan when every job has a positive tail. We propose a polynomial approximation algorithm with a worst-case performance ratio of 3/2 for this problem. We show that this bound is tight. We present a dynamic programming algorithm and we show that the problem has an FPTAS (Fully Polynomial Time Approximation Algorithm) by exploiting the well-known approach of Ibarra and Kim (J. ACM 22:463–468, 1975). Such an FPTAS is strongly polynomial. The obtained results outperform the previous polynomial approximation algorithms for this problem.     

Solution of a single stage machine load planning problem

A subgradient algorithm and a binary integer assignment algorithm are used in tandem to determine economic run quantities for an injection molding facility. The model considers machine regular time and overtime capability, machine-tool compatibility, storage area capacity, and the economics of lot size decisions. Use of the model in scheduling and alternative facility evaluation are discussed.     

Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints

This research deals with scheduling jobs on unrelated parallel machines with auxiliary equipment constraints. Each job has a due date and requires a single operation. A setup for dies is incurred if there is a switch from processing one type of job to another type. For a die type, the number of dies is limited. Due to the attributes of the machines and the fitness of dies to each, the processing time for a job depends on the machine on which the job is processed, each job being restricted to processing on certain machines. In this paper, an effective heuristic based on threshold-accepting methods, tabu lists, and improvement procedures is proposed to minimize total tardiness. An extensive experiment is conducted to evaluate the computational characteristics of the proposed heuristic. Computational experiences demonstrate that the proposed heuristic is capable of obtaining optimal solutions for small-sized problems, and significantly outperforms an ATCS procedure and a simulated annealing method for problems in larger sizes.