Search

In this paper, we consider the following two-machine no-wait flow shop scheduling problem with two competing agents F 2 | M 1 → M 2 , M 2 , p ij A = p , n o - w a i t | C max A : C max B ≤ Q : Given a set of n jobs J = { J 1 , J 2 , … , J n } and two competing agents A and B. Agent A is associated with a set of n A jobs J A = { J 1 A , J 2 A , … , J n A A } to be processed on the machine M 1 first and then on the machine M 2 with no-wait constraint, and agent B is associated with a set of n B jobs J B = { J 1 B , J 2 B , … , J n B B } to be processed on the machine M 2 only, where the processing times for the jobs of agent A are all the same (i.e., p ij A = p ), J = J A ∪ J B and n = n A + n B . The objective is to build a schedule π of the n jobs that minimizing the makespan of agent A while maintaining the makespan of agent B not greater than a given value Q. We first show that the problem is polynomial time solvable in some special cases. For the non-solvable case, we present an O (n log n) -time (1 + 1 n A + 1) -approximation algorithm and show that this ratio of (1 + 1 n A + 1) is asymptotically tight. Finally, (1 + ϵ) -approximation algorithms are provided. [ABSTRACT FROM AUTHOR]

This paper tackles the two-machine chain-reentrant flow shop scheduling problem with the no-wait constraint; we assume that each job passes from the first machine to the second and returns back to the first machine in order to execute its last operation. The objective is to minimize the makespan. In this work, we prove that the symmetric case of this problem, which is proven to be N P -hard in the strong sense, remains N P -hard. Then we provide two polynomial subproblems. For the main problem’s resolution, we propose two new efficient heuristics as well as two improved lower bounds that consistently outperform the existing methods. Additionally, we provide an effective Branch & Bound algorithm that can solve up to 100 jobs for some types of instances. These contributions not only enhance the theoretical comprehension of the problem but also offer efficient solutions supported by extensive statistical analysis over randomly generated instances. [ABSTRACT FROM AUTHOR]

Multiprocessor scheduling, also called scheduling on parallel identical machines to minimize the makespan, is a classic optimization problem which has been extensively studied. Scheduling with testing is an online variant, where the processing time of a job is revealed by an extra test operation, otherwise the job has to be executed for a given upper bound on the processing time. Albers and Eckl recently studied the multiprocessor scheduling with testing; among others, for the non-preemptive setting they presented an approximation algorithm with competitive ratio approaching 3.1016 when the number of machines tends to infinity and an improved approximation algorithm with competitive ratio approaching 3 when all test operations take one unit of time each. We propose to first sort the jobs into non-increasing order of the minimum value between the upper bound and the testing time, then partition the jobs into three groups and process them group by group according to the sorted job order. We show that our algorithm achieves better competitive ratios, which approach 2.9513 when the number of machines tends to infinity in the general case; when all test operations each takes one time unit, our algorithm achieves even better competitive ratios approaching 2.8081. [ABSTRACT FROM AUTHOR]

This paper addresses the online parallel machine scheduling problem with machine leasing discount. Rental cost discount is a common phenomenon in the sharing manufacturing environment. In this problem, jobs arrive one by one over-list and must be allocated irrevocably upon their arrivals without knowing future jobs. Each job is with one unit of processing time. One manufacturer leases a limited number of identical machines over a manufacturing resource sharing platform, and pays a rental fee of α per time unit for processing jobs. Especially, when the time duration of a leasing machine reaches the discount time point, the manufacturer will get a discount for further processing jobs on the machine, i.e., the unit time rental cost is α β , where β = 1 / 2 is the discount coefficient. The objective function is the sum of makespan and the rental cost of all the sharing machines. When the unit time rental cost α ≥ 2 , we first provide the lower bound of objective value of an optimal schedule in the offline version and prove a lower bound of 1.093 for the problem. Based on the analysis of the offline solution, we present a deterministic online algorithm LS-RD with a tight competitive ratio of 3/2. When 1 ≤ α < 2 , we prove that the competitive ratios of algorithm LIST are 1 and 2 for the case of m = 2 and m → ∞ , respectively. For the general rental discount 0 < β ≤ 1 , we give the relevant results for offline and online solutions. [ABSTRACT FROM AUTHOR]

We consider a number of parallel-machine scheduling problems in which jobs have variable processing times. The actual processing time of each job is described by an arbitrary positive function of the position it holds on a machine. However, the function itself may additionally depend on the job or a machine this job was assigned to. Our aim is to find a schedule that minimizes the objectives of maximum completion time or the total completion time. We present a full set of polynomial solutions for the cases of jobs with no precedence constraints. We also show that the case of single-chained jobs may be not easier in general, but some polynomial results can be obtained, too. [ABSTRACT FROM AUTHOR]

Multiprocessor open shop makes a generalization to classical open shop by allowing parallel machines for the same task. Scheduling of this shop environment to minimize the makespan is a strongly NP-Hard problem. Despite its wide application areas in industry, the research in the field is still limited. In this paper, the proportionate case is considered where a task requires a fixed processing time independent of the job identity. A novel highly efficient solution representation is developed for the problem. An ant colony optimization model based on this representation is proposed with makespan minimization objective. It carries out a random exploration of the solution space and allows to search for good solution characteristics in a less time-consuming way. The algorithm performs full exploitation of search knowledge, and it successfully incorporates problem knowledge. To increase solution quality, a local exploration approach analogous to a local search, is further employed on the solution constructed. The proposed algorithm is tested over 100 benchmark instances from the literature. It outperforms the current state-of-the-art algorithm both in terms of solution quality and computational time. [ABSTRACT FROM AUTHOR]

In this paper, we study the two-machine no-wait flow shop scheduling problem with two competing agents. The objective is to minimize the overall completion time of one agent subject to an upper bound on the makespan of the second agent. We proved the NP -hardness for three special cases: (1) each agent has exactly two operations. (2) the jobs of one agent require processing only on one machine, (3) the no-wait constraint is only required for the jobs of one agent. We exhibited polynomial time algorithms for other restricted cases. We also proposed a mathematical programming model and a branch and bound scheme as solving approaches for small-scale problems. For large instances, we present a tabu search meta-heuristic algorithm. An intensive experimental study is conducted to illustrate the effectiveness of the proposed exact and approximation algorithms. [ABSTRACT FROM AUTHOR]

The paper on hand approaches the classical makespan minimization problem on identical parallel machines from a rather theoretical point of view. Using an approach similar to the idea behind inverse optimization, we identify a general structural pattern of optimal multiprocessor schedules. We also show how to derive new dominance rules from the characteristics of optimal solutions. Results of our computational study attest to the efficacy of the new rules. They are particularly useful in limiting the search space when each machine processes only a few jobs on average. [ABSTRACT FROM AUTHOR]

Production systems are subject to machine deterioration and resource consumption constraints. The deterioration increases the processing time which leads to an increase in resource consumption. In this study, we investigate and model the behavior of a parallel machine scheduling problem with respect to the processing time. The machine is subject to deterioration and includes two resource consumption constraints. The first resource R1 controls the processing time so that additional amounts of R1 decrease the processing time. The second R2 is controlled by the actual processing time so that R2 consumption is a linear function of the actual processing time. The increment of R1 consumption leads to processing time and so R2 decrement. Solving this problem consists in finding the optimal schedule that will minimize both makespan and resources cost. This paper provides a mathematical programming model. In fact, due to the deterioration effect and the two resource consumptions, solving such a problem may be very difficult and requires a large computational time. In this paper, we introduce a multi objective simulated annealing (MOSA) in order to solve the combinatorial optimization problem related to finding the best combination (machine, job, position, R1). Literally the best jobs assignment and resources allocation so that makespan and resources cost are minimized. In order to improve the quality of the results we also developed a 2-steps algorithm by decomposing the original problem into two sub problems: an assignment problem and a resources allocation problem. Some simulations were performed to analyze the performances of the two algorithms. The results show that the 2-steps algorithm is very efficient and outperforms MOSA. [ABSTRACT FROM AUTHOR]

We consider problem P 2 | | C max where the goal is to schedule n jobs on two identical parallel machines to minimize the makespan. We focus on constant factor approximation algorithms with complexity independent from the required accuracy. We exploit the famous Longest Processing Time (LPT) rule that requires to sort jobs in non-ascending order of processing times and then to assign one job at a time to the machine whose load is smallest so far. We propose an approximation algorithm that applies LPT to a subset of 2k jobs, then considers a single step of local search on the obtained subschedule and finally applies list scheduling to the remaining jobs. This algorithm, when applied for k = 5 , reaches a tight 13 12 -approximation ratio improving the ratio of 12 11 proposed by He et al. (Nav Res Logist 47:593–601, 2000). We use Mathematical Programming to analyze the approximation ratio of our approach. As a byproduct, we also show how to improve the FPTAS of Sahni for any n > 1 / ϵ so as to reach an approximation ratio (1 + ϵ) with time complexity O (n + 1 ϵ 3) . [ABSTRACT FROM AUTHOR]

A two-stage openshop consists of a machine in the first stage and a machine in the second stage; a job processed on the two-stage openshop means it is processed non-preemptively by each of the two machines, in whichever order. We consider the scheduling problem at the availability of multiple parallel identical two-stage openshops, with the goal to minimize the makespan. By uncovering the important role of the critical job in the optimal schedule on a two-stage openshop, we propose to sort the jobs in the novel critical-job order, and use this order to design a pseudo-polynomial time dynamic programming exact algorithm to solve our scheduling problem with any fixed number of two-stage openshops. Afterwards, using the standard scaling technique, we develop the dynamic programming algorithm into a fully polynomial-time approximation scheme. These results improve previously proposed constant ratio approximation algorithms. [ABSTRACT FROM AUTHOR]

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≥3. In this paper, we present a best possible online algorithm for the problem with m≥3, where the algorithm has a competitive ratio of 1.3028 for 3≤m≤5 and 1.3146 for m≥6. [ABSTRACT FROM AUTHOR]

We study the multi-agent scheduling on a single machine with a fixed number of competing agents, in which, the objective function of each agent is either the number of tardy jobs or the makespan, and the goal of the problem is to minimize the weighted sum of agents' objective functions. In the literature, the computational complexity of this problem was posed as open. By using enumerating, dynamic programming, and schedule-configuration, we show in this paper that the problem is solvable in polynomial time. [ABSTRACT FROM AUTHOR]

This paper considers the large-scale mixed job shop scheduling problem with general number of jobs on each route. The problem includes ordinary machines, batch machines (with bounded or unbounded capacity), parallel machines, and machines with breakdowns. The objective is to find a schedule to minimize the makespan. For the problem, we define a virtual problem and a corresponding virtual schedule, based on which our algorithm TVSA is proposed. The performance analysis of the algorithm shows the gap between the obtained solution and the optimal solution is O(1), which indicates the algorithm is asymptotically optimal. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

A two-agent scheduling problem on parallel machines is considered. Our objective is to minimize the makespan for agent A, subject to an upper bound on the makespan for agent B. When the number of machines, denoted by $$m$$ , is chosen arbitrarily, we provide an $$O(n)$$ algorithm with performance ratio $$2-\frac{1}{m}$$ , i.e., the makespan for agent A given by the algorithm is no more than $$2-\frac{1}{m}$$ times the optimal value, while the makespan for agent B is no more than $$2-\frac{1}{m}$$ times the threshold value. This ratio is proved to be tight. Moreover, when $$m=2$$ , we present an $$O(nlogn)$$ algorithm with performance ratio $$\frac{1+\sqrt{17}}{4}\approx 1.28$$ which is smaller than $$\frac{3}{2}$$ . The ratio is weakly tight. [ABSTRACT FROM AUTHOR]

This paper considers a single-machine scheduling with linear deterioration rate of processing speed and multiple rate-modifying activities simultaneously. A rate-modifying activity can change the processing rate of machine under consideration, which means after each rate-modifying activity the speed of the machine is fully recovered. The integration of these two concept is motivated by human operators and semi-automatic systems that experience performance degradation over time and require rate-modifying activities for recovery. The objective is to minimize the makespan. We need to decide the sequence of jobs and when to schedule the rate-modifying activities. An optimal schedule is proposed, which can solve the problem in $$O(n\log n)$$ time where $$n$$ is the number of jobs. [ABSTRACT FROM AUTHOR]

We consider a scheduling problem in which jobs are processed on two identical parallel machines that share a common server that loads and unloads jobs on them. Each job has to be loaded by the server before being processed on one of the machines and unloaded immediately by the server after its processing. The goal is to minimize the makespan. We study non-preemptive variants of the problem where the loading and unloading times are both equal to one time unit. Since the non-preemptive variant of the problem is NP-hard, we apply two classical heuristics, namely list scheduling (LS) and longest processing time (LPT),to tackle the problem. We show that LS and LPT have tight worst-case ratios of 12/7 and 4/3, respectively. [ABSTRACT FROM AUTHOR]

In previous study on comparing the makespan of the schedule allowed to be preempted at most i times and that of the optimal schedule with unlimited number of preemptions, the worst case ratio was usually obtained by analyzing the structures of the optimal schedules. For m identical machines case, the worst case ratio was shown to be 2 m/( m+ i+1) for any 0≤ i≤ m−1 (Braun and Schmidt in SIAM J. Comput. 32(3):671-680, ), and they showed that LPT algorithm is an exact algorithm which can guarantee the worst case ratio for i=0. In this paper, we propose a simpler method which is based on the design and analysis of the algorithm and finding an instance in the worst case. It can not only obtain the worst case ratio but also give a linear algorithm which can guarantee this ratio for any 0≤ i≤ m−1, and thus we generalize the previous results. We also make a discussion on the trade-off between the objective value and the number of preemptions. In addition, we consider the i-preemptive scheduling on two uniform machines. For both i=0 and i=1, we give two linear algorithms and present the worst-case ratios with respect to s, i.e., the ratio of the speeds of two machines. [ABSTRACT FROM AUTHOR]

We study the problems of non-preemptively scheduling and packing malleable and parallel tasks with precedence constraints to minimize the makespan. In the scheduling variant, we allow the free choice of processors; in packing, each task must be assigned to a contiguous subset. Malleable tasks can be processed on different numbers of processors with varying processing times, while parallel tasks require a fixed number of processors. For precedence constraints of bounded width, we resolve the complexity status of the problem with any number of processors and any width bound. We present an FPTAS based on Dilworth's decomposition theorem for the NP-hard problem variants, and exact efficient algorithms for all remaining special cases. For our positive results, we do not require the otherwise common monotonous penalty assumption on the processing times of malleable tasks, whereas our hardness results hold even when assuming this restriction. We complement our results by showing that these problems are all strongly NP-hard under precedence constraints which form a tree. [ABSTRACT FROM AUTHOR]

This article studies a single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity. We assume that after maintenance activity, the machine will revert to its initial condition and the aging effects will start anew. Moreover, due to the restriction of budget of maintenance, the limitation of the maintenance frequency on the machine is assumed to be known in advance. The optional maintenance activity of this study means that the starting time of the maintenance activity is unknown in advance. It can be scheduled immediately after the processing of any job that has been completed. Therefore, the planner must to make decision on whether or when to schedule the maintenance activity during the scheduling horizon to optimal the performance measures. The objective is to minimize the makespan. We first show that the addressed problem is NP-hard in the strong sense. Then a fully polynomial-time approximation scheme (FPTAS) for the proposed problem is presented. [ABSTRACT FROM AUTHOR]

In this paper we study the optimality of the TLS algorithm for solving the online scheduling problem of minimizing the makespan on a set of m multipurpose machines, where there are two different job types and each job type can only be processed on a unique subset of machines. The literature shows that the TLS algorithm is optimal for the special cases where either m=2 or where all processing times are restricted to unity. We show that the TLS algorithm is optimal also for the special cases where the job processing times are either job type or machine set dependent. For both cases, the optimality of the TLS algorithm is proven by showing that its competitive ratio matches the lower bound for any processing set and processing time parameters. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We consider a generalization of the proportionate flow shop problem with the makespan objective. Each job has a processing requirement and each machine has a characteristic value. In our case, we assume that the time a job occupies a machine is equal to the processing requirement of the job plus a setup time that is equal to the characteristic value of that machine. In this paper, we consider permutation schedules and show that the problem is solvable in polynomial time when the number of machines is fixed. [ABSTRACT FROM AUTHOR]

We study the problem of semi-online scheduling on 2 machines under a grade of service (GoS). GoS means that some jobs have to be processed by some machines to be guaranteed a high quality. The problem is online in the sense that jobs are presented one by one, and each job shall be assigned to a time slot on its arrival. Assume that the processing time p of every job J is bounded by an interval [ a, α a], where a>0 and α>1 are two constant numbers. By knowing the bound of jobs' processing times, we denote it by semi-online problem. We deal with two semi-online problems. The first one concerns about bounded processing time constraint. First, we show that a lower bound of competitive ratio is: (1) $\frac{1+\alpha}{2}$ in the case where 1< α<2; (2) $\frac{3}{2}$ in the case where 2≤ α<5; and (3) $\frac{4+\alpha}{6}$ in the case where 5≤ α<6. We further propose an algorithm, called B-ONLINE, and prove that in the case where $\frac{25}{14}\leq \alpha$ and the optimal makespan C≥20 a, B-ONLINE algorithm is optimal. For the second problem, we further know the sum of jobs' processing times Σ in advance. We first show a lower bound $\frac{1+\alpha}{2}$ in the case where 1< α<2, then we propose an algorithm B-SUM-ONLINE which is optimal in the case where $\Sigma \geq \frac{2\alpha}{\alpha-1}a$ and 1< α<2. [ABSTRACT FROM AUTHOR]

We investigate the problem of on-line scheduling two-machine open shops with the objective of minimizing the makespan.Jobs arrive independently over time, and the existence of a job is not known until its arrival. In the clairvoyant on-line model, the processing requirement of every job becomes fully known at the arrival of the job, while inthe non-clairvoyant on-line model, this processing requirement is notknown until the job is processed and completed.In both models, scheduling of a job is irrevocable. We study the two-machine open shop problem for both models in the preemptive and in the non-preemptive version. For each of the four variants, we provide an algorithm that is best possible with respect to the worst-case performance. In the clairvoyant on-line model, the best worst-case performance ratios are 5/4 (preemptive) and 3/2 (non-preemptive), and in the non-clairvoyant on-line model, they are 3/2 (preemptive and non-preemptive). [ABSTRACT FROM AUTHOR]