A note on special optimal batching structures to minimize total weighted completion time

A batch is a subset of jobs which must be processed jointly in either serial or parallel form. The algorithmic aspects of the batching scheduling problems have been extensively studied in the literature. This paper presents necessary and sufficient conditions of the existence of optimal batch sequences for the single machine, batching, total weighted completion time scheduling problems on two batching ways: (1) all jobs form one batch; (2) each batch contains a single job. This kind of conditions can help us to recognize some special optimal schedules quickly. Research supported by NSFC (10671183).     

One-machine scheduling to minimize mean tardiness with minimum number tardy

In this paper the one-machine scheduling problem with the objective of minimizing the mean tardiness subject to maintaining a prescribed number of tardy jobs is analysed. An algorithm for solving this problem is presented. It is proved that the schedule generated by the proposed algorithm is indeed optimal.     

A note on pre-emptive scheduling with earliness and tardiness costs

The option of pre-emption seems to have escaped the attention of existing literature on scheduling problems with earliness and tardiness costs. This note presents an attempt to accommodate pre-emption in such settings. The focus is on models with a common due date for all jobs under different cost structures ( job dependent versus job independent), and different objectives ( minsum and minmax). It appears that only one of these cases is not polynomially solvable: the case of minsum objective and job-dependent ( linear) cost. An exact dynamic programming algorithm is introduced for this problem, as well as an efficient heuristic, which is shown to perform extremely well in our numerical tests.     

A heuristic to minimize total flow time in permutation flow shop

In this paper, we address an n-job, m-machine permutation flow shop scheduling problem for the objective of minimizing the total flow time. We propose a modification of the best-known method of Framinan and Leisten [An efficient constructive heuristic for flowtime minimization in permutation flow shops. Omega 2003;31:311–7] for this problem. We show, through computational experimentation, that this modification significantly improves its performance while not affecting its time-complexity.     

Two-agent scheduling problems on a single-machine to minimize the total weighted late work

In this paper, two-agent scheduling problems are presented. The different agents share a common processing resource, and each agent wants to minimize a cost function depending on its jobs only. The objective functions we consider are the total weighted late work and the maximum cost. The problem is to find a schedule that minimizes the objective function of agent A, while keeping the objective function of agent B cannot exceed a given bound U. Some different scenarios are presented by depending on the objective function of each agent. We address the complexity of those problems, and present the optimal polynomial time algorithms or pseudo-polynomial time algorithm to solve the scheduling problems, respectively.     

Customer order scheduling to minimize total weighted completion time

In this paper we study the scheduling problem in which each customer order consists of several jobs of different types, which are to be processed on m facilities. Each facility is dedicated to the processing of only one type of jobs. All jobs of an order have to be delivered to the customer at the same time. The objective is to schedule all the orders to minimize the total weighted order completion time. While the problem has been shown to be unary NP-hard, we develop a heuristics to tackle the problem and analyze its worst-case performance.     

Some heuristic algorithms for total tardiness minimization in a flowshop with blocking

The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines; therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising.     

A note on domination and total domination in prisms

Recently, Azarija et al. (Electron J Combin:1.19, 2017) considered the prism \(G \mathop {\square }K_2\) of a graph G and showed that \(\gamma _t(G \mathop {\square }K_2) = 2\gamma (G)\) if G is bipartite, where \(\gamma _t(G)\) and \(\gamma (G)\) are the total domination number and the domination number of G. In this note, we give a simple proof and observe that there are similar results for other pairs of parameters. We also answer a question from that paper and show that for all graphs \(\gamma _t(G \mathop {\square }K_2) \ge \frac{4}{3}\gamma (G)\), and this bound is tight.     

Online scheduling to minimize the total weighted completion time plus the rejection cost

We consider the online scheduling on a single machine, in which jobs are released over time and each job can be either accepted and scheduled on the machine or rejected under a certain rejection cost. The goal is to minimize the total weighted completion time of the accepted jobs plus the total rejection cost of the rejected jobs. For this problem, we provide an online algorithm with a best possible competitive ratio of 2.     

An optimal online algorithm for single machine scheduling to minimize total general completion time

We study the online problem of single machine scheduling to minimize total general completion time. General completion time is defined as C^a_j=(C_j)^aC^{\alpha}_{j}=(C_{j})^{\alpha}, where C _j denotes the completion time of job J _j and α≥1 is a constant integer. Total general completion time characterizes the feather in service that when a customer is served later in time, his dissatisfaction increases in a manner of power function. The objective function ∑(C _j ) ^α can also be viewed as a total weighted completion time, but the “weight” is no longer a constant number. Our purpose to minimize customers’ total dissatisfaction. The problem is online in the sense that all jobs arrive over time. Each job’s processing time becomes known at its arrival time. Preemption is not allowed. For this online problem, we show that a lower bound on competitive ratio is 2 ^α and prove that D-SPT (delayed shortest processing time) algorithm is optimal with a competitive ratio 2 ^α .     

Single-machine scheduling with periodic due dates to minimize the total earliness and tardy penalty

We consider a single-machine scheduling problem such that the due dates are assigned to each job depending on its order, and the lengths of the intervals between consecutive due dates are identical. The objective is to minimize the total penalty for the earliness and tardiness of each job. The early penalty proportionally increases according to the earliness amount, while the tardy penalty increases according to the step function. We show that the problem is strongly NP-hard, and furthermore, polynomially solvable if the two types of processing times exist.

     

Distance constrained vehicle routing problem to minimize the total cost: algorithms and complexity

Journal of Combinatorial Optimization - Given $$\lambda >0$$ , an undirected complete graph $$G=(V,E)$$ with nonnegative edge-weight function obeying the triangle inequality and a depot...     

A fast FPTAS for single machine scheduling problem of minimizing total weighted earliness and tardiness about a large common due date

We address the single machine scheduling problem to minimize the total weighted earliness and tardiness about a nonrestrictive common due date. This is a basic problem with applications to the just-in-time manufacturing. The problem is linked to a Boolean programming problem with a quadratic objective function, known as the half-product. An approach to developing a fast fully polynomial-time approximation scheme (FPTAS) for the problem is identified and implemented. The running time matches the best known running time for an FPTAS for minimizing a half-product with no additive constant.     

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%.     

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}\).     

Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach

In today's fast-paced Just-In-Time and mass customization manufacturing in a sequence-dependent setup environment, the challenge of making production schedules to meet due-date requirements is becoming a more complex problem. Unfortunately, much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. This paper considers the problem of minimizing tardiness, a common measure of due-date performance, in a sequence-dependent setup environment. Simulated annealing was used to solve the sequencing problem, and its performance was compared with random search. Our experimental results show that the algorithm can find a good solution fairly quickly, and thus can rework schedules frequently to react to variations in the schedule. The algorithm is invaluable for ‘on-line’ production scheduling and ‘last-minute’ changes to production schedule. The results of this research also suggest ways in which more complex and realistic job shop environments, such as multiple machines with a higher number of jobs in the sequence, and other scheduling objectives can be modeled. This research also investigates computational aspects of simulated annealing in solving complex scheduling problems.     

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.     

A note on online strip packing

In online strip packing we are asked to pack a list of rectangles one by one into a vertical strip of unit width, without any information about future rectangles. The goal is to minimize the total height of strip used. The best known algorithm is First Fit Shelf algorithm (Baker and Schwarz in SIAM J. Comput. 12(3):508–525, 1983), which has an absolute competitive ratio of 6.99 under the assumption that the height of each rectangle is bounded from above by one. We improve the shelf algorithm and show an absolute competitive ratio of without the restriction on rectangle heights. Our algorithm also beats the best known online algorithm for parallel job scheduling. Ye’s research supported by NSFC(10601048). Zhang’s research supported by NSFC(60573020).