Single-machine scheduling problems with a learning effect

In many situations, the skills of workers continuously improve when repeating the same or similar tasks. This phenomenon is known as the “learning effect” in the literature. In most studies, the learning phenomenon is implemented by assuming the actual job processing time is a function of its scheduled position [D. Biskup, Single-machine scheduling with learning considerations, Eur. J. Oper. Res. 115 (1999) 173–178]. Recently, a new model is proposed where the actual job processing time depends on the sum of the processing times of jobs already processed [C. Koulamas, G.J. Kyparisis, Single-machine and two-machine flowshop scheduling with general learning functions, Eur. J. Oper. Res. 178 (2007) 402–407]. In this paper, we extend their models in which the actual job processing time not only depends on its scheduled position, but also depends on the sum of the processing times of jobs already processed. We then show that the single-machine makespan and the total completion time problems remain polynomially solvable under the proposed model. In addition, we show that the total weighted completion time has a polynomial optimal solution under certain agreeable solutions.     

Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan

We consider a scheduling problem in which n jobs are to be processed on a single machine. The jobs are processed in batches and the processing time of each job is a simple linear function of its waiting time, i.e., the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. The objective is to minimize the makespan, i.e., the completion time of the last job. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B  , the problem remains strongly NP-hard when B?U$B?U$ for a variable U?2$U?2$ or B?U$B?U$ for any constant U?2$U?2$. For the case of B?U$B?U$, we present a dynamic programming algorithm that runs in pseudo-polynomial time and a fully polynomial time approximation scheme (FPTAS) for any constant U?2$U?2$. Furthermore, we provide an optimal linear time algorithm for the special case where the jobs are subject to a linear precedence constraint, which subsumes the case where all the job growth rates are equal.     

Online scheduling of ordered flow shops

We consider online as well as offline scheduling of ordered flow shops with the makespan as objective. In an online flow shop scheduling problem, jobs are revealed to a decisionmaker one by one going down a list. When a job is revealed to the decision maker, its operations have to be scheduled irrevocably without having any information regarding jobs that will be revealed afterwards. We consider for the online setting the so-called Greedy Algorithm which generates permutation schedules in which the jobs on the machines are at all times processed without any unnecessary delays. We focus on ordered flow shops, in particular proportionate flow shops with different speeds and proportionate flow shops with different setup times. We analyze the competitive ratio of the Greedy Algorithm for such flow shops in the online setting. For several cases, we derive lower bounds on the competitive ratios.     

A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal

The scheduling problem in a container terminal is characterized by the coordination of different types of equipment. In this paper, we present an integrated model to schedule the equipment. The objective is to minimize the makespan, or the time it takes to serve a given set of ships. The problem is formulated as a Hybrid Flow Shop Scheduling problem with precedence and Blocking constraints (HFSS-B). A tabu search algorithm is proposed to solve this problem. Certain mechanisms are developed and introduced into the algorithm to assure its quality and efficiency. The performance of the tabu search algorithm is analyzed from the computational point of view.     

Erratum to “Single-machine scheduling problems with both deteriorating jobs and learning effects” [Appl. Math. Modell. 34 (2010) 2831–2839]

The aim of this paper is to show by counterexamples that Theorems 3–10 and Corollaries 2–5 in Wang et al. [Appl. Math. Model. 34 (2010) 2831–2839] are incorrect.     

Makespan minimization in open shops: A polynomial time approximation scheme

In this paper, we demonstrate the existence of a polynomial time approximation scheme for makespan minimization in the open shop scheduling problem with an arbitrary fixed numberm of machines. For the variant of the problem where the number of machines is part of the input, it is known that the existence of an approximation scheme would implyP = NP. Hence, our result draws a precise separating line between approximable cases (i.e., withm fixed) and non-approximable cases (i.e., withm part of the input) of this shop problem. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by the DIMANET/PECO Program of the European Union.Supported by a research fellowship of the Euler Institute for Discrete Mathematics and its Applications. This research was done while Gerhard Woeginger was with the Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, NL-5600 MB Eindhoven, The Netherlands.     

Open shop scheduling problem to minimize makespan with release dates

The scheduling problem of open shop to minimize makespan with release dates is investigated in this paper. Unlike the usual researches to confirm the conjecture that the tight worst-case performance ratio of the Dense Schedule (DS) is 2 − 1/m, where m is the number of machines, the asymptotic optimality of the DS is proven when the problem scale tends to infinity. Furthermore, an on-line heuristic based on DS, Dynamic Shortest Processing Time-Dense Schedule, is presented to deal with the off-line and on-line versions of this problem. At the end of the paper, an asymptotically optimal lower bound is provided and the results of numerical experiments show the effectiveness of the heuristic.     

Heuristic solution methods for the stochastic flow shop problem

We investigate the stochastic flow shop problem with m machines and general distributions for processing times. No analytic method exists for solving this problem, so we looked instead at heuristic methods. We devised three constructive procedures with modest computational requirements, each based on approaches that have been successful at solving the deterministic counterpart. We compared the performance of these procedures experimentally on a set of test problems and found that all of them achieve near-optimal performance.     

Makespan minimization in machine dominated flowshop

In a flowshop scheduling problem, a set of jobs is processed by a set of machines. The jobs follow the same sequence in all machines. We study the flowshop scheduling problem under a new case of machine dominance that is often found in the manufacturing of computers and electronic devices. We provide a formula for makespan value for a given sequence, show that the makespan value depends only on certain jobs in the sequence, and present an algorithm that finds a sequence with minimum makespan. Numerical examples of the solution approaches are provided.