Online lazy bureaucrat scheduling with a machine deadline

The lazy bureaucrat scheduling problem was first introduced by Arkin et al. (Inf Comput 184:129–146, 2003). Since then, a number of variants have been addressed. However, very little is known on the online version. In this note we focus on the scenario of online scheduling, in which the jobs arrive over time. The bureaucrat (machine) has a working time interval. Namely, he has a deadline by which all scheduled jobs must be completed. A decision is only based on released jobs without any information on the future. We consider two objective functions of [min-makespan] and [min-time-spent]. Both admit best possible online algorithms with competitive ratio of \(\frac{\sqrt{5}+1}{2}\approx 1.618\).     

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.     

A general modeling approach to online optimization with lookahead

A vast number of real world problems are coined by an information release over time and the related need for repetitive decision making over time. Optimization problems arising in this context are called online since decisions have to be made although not all data is known. Due to technological advances, algorithms may also resort to a limited preview (lookahead) on future events. We first embed the paradigm of online optimization with lookahead into the theory of optimization and develop a concise understanding of lookahead. We further find that the effect of lookahead can be decomposed into an informational and a processual component. Based on analogies to discrete event systems, we then formulate a generic modeling framework for online optimization with lookahead and derive a classification scheme which facilitates a thorough categorization of different lookahead concepts. After an assessment of performance measurement approaches with relevance to practical needs, we conduct a series of computational experiments which illustrate how the general concept of lookahead applies to specific instantiations and how a knowledge pool on lookahead effects in applications can be built up using the general classification scheme.     

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.     

Online scheduling on a single machine with linear deteriorating processing times and delivery times

Journal of Combinatorial Optimization - This paper considers a class of problems with linear deteriorating jobs. Jobs are released over time and become known to the online scheduler until their...     

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

Euclidean movement minimization

We consider a class of optimization problems called movement minimization on euclidean plane. Given a set of \(m\) nodes on the plane, the aim is to achieve some specific property by minimum movement of the nodes. We consider two specific properties, namely the connectivity (Con) and realization of a given topology (Topol). By minimum movement, we mean either the sum of all movements (Sum) or the maximum movement (Max). We obtain several approximation algorithms and some hardness results for these four problems. We obtain an \(O(m)\)-factor approximation for ConMax and ConSum and extend some known result on graphical grounds and obtain inapproximability results on the geometrical grounds. For the Topol problems (where the final decoration of the nodes must correspond to a given configuration), we find it much simpler and provide FPTAS for both Max and Sum versions.     

Related machine scheduling with machine speeds satisfying linear constraints

Journal of Combinatorial Optimization - We propose a related machine scheduling problem in which the processing times of jobs are given and known, but the speeds of machines are variables and must...     

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.     

Makespan and workstation utilization minimization in a flowshop with operations flexibility

Production environments where there are more tasks than workstations and any task can be assigned to any workstation are examples of operations flexibility. This paper investigates the benefits of operations flexibility in a flowshop when the goals are to minimize the makespan and workstation utilization. Furthermore, machine dominance principles are extended to the case of a flowshop with operations flexibility. The proposed heuristic framework comprises of two phases, allocation of operations to workstations and generation of job sequencing. In addition, an improvement procedure based on simulated annealing is implemented for this problem. The experimental results identify the effects of the experimental factors; show the significance of the heuristic factor; and demonstrate the tradeoff between the two performance criteria.     

Randomized Online Scheduling with Delivery Times

We study one of the most basic online scheduling models, online one machine scheduling with delivery times where jobs arrive over time. We provide the first randomized algorithm for this model, show that it is 1.55370-competitive and show that this analysis is tight. The best possible deterministic algorithm is 1.61803-competitive. Our algorithm is a distribution between two deterministic algorithms. We show that any such algorithm is no better than 1.5-competitive. To our knowledge, this is the first lower bound proof for a distribution between two deterministic algorithms.     

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

Profile minimization on compositions of graphs

The profile minimization problem arose from the study of sparse matrix technique. In terms of graphs, the problem is to determine the profile of a graph G which is defined as $$P(G)=\min\limits_{f}\sum\limits_{v\in V(G)}\max\limits_{x\in N[v]}(f(v)-f(x)),$$ where f runs over all bijections from V(G) to {1,2,…,|V(G)|} and N[v]={v}∪{x∈V(G):xv∈E(G)}. This is equivalent to the interval graph completion problem, which is to find a super-graph of a graph G with as few number of edges as possible. The purpose of this paper is to study the profiles of compositions of two graphs.     

Scheduling with machine cost and rejection

In this paper we consider the scheduling problem with machine cost and rejection penalties. For this problem, we are given a sequence of independent jobs, each being characterized by its processing time (size) and its penalty. No machine is initially provided, and when a job is revealed the algorithm has the option to purchase new machines. Right when a new job arrives, we have the following choices: (i) reject it, in which case we pay its penalty; (ii) non-preemptively process it on an existing machine, which contributes to the machine load; (iii) purchase a new machine, and assign it to this machine. The objective is to minimize the sum of the makespan, the cost for purchasing machines, and the total penalty of all rejected jobs. For the small job case, (where all jobs have sizes no greater than the cost for purchasing one machine, and which is the generalization of the Ski-Rental Problem) we present an optimal online algorithm with a competitive ratio of 2.     

On-line machine scheduling with batch setups

We study a class of scheduling problems with batch setups for the online-list and online-time paradigms. Jobs are to be scheduled in batches for processing. All jobs in a batch start and complete together, and a constant setup is prior to each batch. The objective is to minimize the total completion time of all jobs. We primarily consider the special cases of these problems with identical processing times, for which efficient on-line heuristics are proposed and their competitive performance is evaluated.     

Online tree node assignment with resource augmentation

Given a complete binary tree of height h, the online tree node assignment problem is to serve a sequence of assignment/release requests, where an assignment request, with an integer parameter 0≤i≤h, is served by assigning a (tree) node of level (or height) i and a release request is served by releasing a specified assigned node. The node assignments have to guarantee that no node is assigned to two assignment requests unreleased, and every leaf-to-root path of the tree contains at most one assigned node. With assigned node reassignments allowed, the target of the problem is to minimize the number of assignments/reassignments, i.e., the cost, to serve the whole sequence of requests. This online tree node assignment problem is fundamental to many applications, including OVSF code assignment in WCDMA networks, buddy memory allocation and hypercube subcube allocation.     

Resource smoothing: A cost minimization approach

From the available literature, there seems to be no defined approach to resource smoothing exercise except those attempted by Weist (1967, Management Science, 13, B359-B377) and Burgess and Killebrew (1962, Journal of Industrial Engineering, 13, 76-83). The aim of the smoothing exercise is to achieve optimal resource usage by avoiding high peaks and deep valleys in the project resource profile. The general approach has always been to move some activities with floats in the high peak regions to be started at a later date, and as this is done, the valleys will be filled to smooth the resource profile subject of course to time constraint. If this approach is followed as it is, it would be difficult to determine optimality especially when many resources are involved. A cost minimization approach is envisaged in the present study with no limitation on the number of resource inputs. In a situation where the resources are assumed to have the same value, the cost assigned to each of them should be similar. The method follows the general concept but with a difference; cost of the activity in question is considered. The exercise is continued until all the floats are exhausted. The optimum result would then be the one with the minimum cost profile. From examples used for the evaluation, the results obtained are comparable to those of the above two researchers, and some with better results in the majority of cases.