On-line algorithms for single machine scheduling with family setup times

The paper considers an on-line single machine scheduling problem where the goal is to minimize the makespan. The jobs are partitioned into families and a setup is performed every time the machine starts processing a batch of jobs of the same family. The scheduler is aware of the number of families and knows the setup time of each family, although information about a job only becomes available when that job is released. We give a lower bound on the competitive ratio of any on-line algorithm. Moreover, for the case of two families, we provide an algorithm with a competitive ratio that achieves this lower bound. As the number of families increases, the lower bound approaches 2, and we give a simple algorithm with a competitive ratio of 2.

An improved approximation algorithm for the two-machine flow shop scheduling problem with an interstage transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables

An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.

Schedules with due-date assignment and position-dependent processing times

Single machine scheduling problems are considered, in which the processing of jobs depend on positions of the jobs in a schedule and the due-dates are assigned either according to the CON rule (a due-date common to all jobs is chosen) or according to the SLK rule (the due-dates are computed by increasing the actual processing times of each job by a slack, common to all jobs). Polynomial-time dynamic programming algorithms are proposed for the problems with the objective functions that include the cost of assigning the due-dates, the total cost of disgarded jobs (which are not scheduled) and, possibly, the total earliness of the scheduled jobs.

Approximation results for flow shop scheduling problems with machine availability constraints

This paper considers two-machine flow shop scheduling problems with machine availability constraints. When the processing of a job is interrupted by an unavailability period of a machine, we consider both the resumable scenario in which the processing can be resumed when the machine next becomes available, and the semi-resumable scenario in which some portion of the processing is repeated but the job is otherwise resumable. For the problem with several non-availability intervals on the first machine under the resumable scenario, we present a fast (3/2)-approximation algorithm. For the problem with one non-availability interval under the semi-resumable scenario, a polynomial-time approximation scheme is developed.

Scheduling parallel dedicated machines with the speeding-up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two-machine problem is NP-hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst-case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple-choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008

Fifty years of scheduling: a survey of milestones

Scheduling has become a major field within operational research with several hundred publications appearing each year. This paper explores the historical development of the subject since the mid-1950s when the landmark publications started to appear. A discussion of the main topics of scheduling research for the past five decades is provided, highlighting the key contributions that helped shape the subject. The main topics covered in the respective decades are combinatorial analysis, branch and bound, computational complexity and classification, approximate solution algorithms and enhanced scheduling models.

Preemptive scheduling on uniform parallel machines with controllable job processing times

In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan.

Start-up and running forces on bulk solids feeders: experimental findings versus available models

Many different models have been postulated over the years for sizing of feeder drives; these models have different bases, some rationally based and others more rule-of-thumb. Experience of Jenike & Johanson and likewise of The Wolfson Centre in trouble-shooting feeder drives has shown that drive powers are often poorly matched, so there is clearly still some way to go towards establishing a universally-used reliable approach. This paper presents an on-going programme of work designed to measure feeder forces experimentally on a purpose designed testing rig, and to compare these against some of the best known available models, and also against a full size installation. One aspect which is novel is the monitoring of the transition between the “filling stress field” load on the feeder and the “flowing stress field” load.

Investigation into a modular rule-based testing method for testing business rules in scheduling applications

Rule testing in transport scheduling is a complex and potentially costly business problem. This paper proposes an automated method for the rule-based testing of business rules using the extensible Markup Language for rule representation and transportation. A compiled approach to rule execution is also proposed for performance-critical scheduling systems.

Social networks and cooperative learning in a MOOC

MOOCs are changing the educational landscape and gaining a lot of attention in scientific literature. However, the pedagogical design of these proposals has been called into question. It is precisely MOOCs’ social aspect, i.e. the interaction between course participants and the support for learning processes that has become one of the main topics of interest. This article presents the results of a research project carried out at the University of the Basque Country, which focused in cooperative learning and the intensive use of social networks in a MOOC. Significant data was compiled through Likert-type surveys, revealing that the use of both external and internal social networks in a massive open online course is a factor that is evaluated positively by students. We argue that the use of social networks as a learning strategy in a MOOC has an influence on academic performance and on the students' success rate. Furthermore, the participants’ age also has a bearing on the social networks they use, and we have found that the younger members tend to work with external networks such as Twitter or personal blogs, whereas the older students are more inclined to use forums from the Chamilo or Ning platforms.

CO oxidation and NO reduction on metal surfaces: density functional theory investigations

This article reviews the accumulated theoretical results, in particular density functional theory calculations, on two catalytic processes, CO oxidation and NO reduction on metal surfaces. Owing to their importance in automotive emission control, these two reactions have generated a lot of interest in the last 20 years. Here the pathways and energetics of the involved elementary reactions under different catalytic conditions are described in detail and the understanding of the reactions is generalized. It is concluded that density functional theory calculations can be applied to catalysis to elucidate mechanisms of complex surface reactions and to understand the electronic structure of chemical processes in general. The achieved molecular knowledge of chemical reactions is certainly beneficial to new catalyst design.