
Journal of Scheduling [SJR: 1.053] [HI: 47] [5 followers] Follow Hybrid journal (It can contain Open Access articles) ISSN (Print) 10991425  ISSN (Online) 10946136 Published by SpringerVerlag [2352 journals] 
 Reordering buffer management with advice
 Authors: Anna Adamaszek; Marc P. Renault; Adi Rosén; Rob van Stee
Pages: 423  442
Abstract: Abstract In the reordering buffer management problem, a sequence of colored items arrives at a service station to be processed. Each color change between two consecutively processed items generates some cost. A reordering buffer of capacity k items can be used to preprocess the input sequence in order to decrease the number of color changes. The goal is to find a scheduling strategy that, using the reordering buffer, minimizes the number of color changes in the given sequence of items. We consider the problem in the setting of online computation with advice. In this model, the color of an item becomes known only at the time when the item enters the reordering buffer. Additionally, together with each item entering the buffer, we get a fixed number of advice bits, which can be seen as information about the future or as information about an optimal solution (or an approximation thereof) for the whole input sequence. We show that for any \(\varepsilon > 0\) there is a \((1+\varepsilon )\) competitive algorithm for the problem which uses only a constant (depending on \(\varepsilon \) ) number of advice bits per input item. This also immediately implies a \((1+\varepsilon )\) approximation algorithm which has \(2^{O(n\log 1/\varepsilon )}\) running time (this should be compared to the trivial optimal algorithm which has a running time of \(k^{O(n)}\) ). We complement the above result by presenting a lower bound of \(\varOmega (\log k)\) bits of advice per request for any 1competitive algorithm.
PubDate: 20171001
DOI: 10.1007/s1095101604878
Issue No: Vol. 20, No. 5 (2017)
 Authors: Anna Adamaszek; Marc P. Renault; Adi Rosén; Rob van Stee
 Online interval scheduling with a bounded number of failures
 Authors: Marco Bender; Clemens Thielen; Stephan Westphal
Pages: 443  457
Abstract: Abstract We consider the problem of scheduling intervals on m identical machines where each interval can be seen as a job with fixed start and end time. The goal is to accept a maximum cardinality subset of the given intervals and assign these intervals to the machines subject to the constraint that no two intervals assigned to the same machine overlap. We analyze an online version of this problem where, initially, a set of n potential intervals and an upper bound k on the number of failing intervals is given. If an interval fails, it can be accepted neither by the online algorithm nor by the adversary. An online algorithm learns that an interval fails at the time when it is supposed to be started. If a nonfailing interval is accepted, it cannot be aborted and must be processed nonpreemptively until completion. For different settings of this problem, we present deterministic and randomized online algorithms and prove lower bounds on the competitive ratio.
PubDate: 20171001
DOI: 10.1007/s1095101605069
Issue No: Vol. 20, No. 5 (2017)
 Authors: Marco Bender; Clemens Thielen; Stephan Westphal
 Mathematical models for the berth allocation problem in dry bulk terminals
 Authors: Andreas T. Ernst; Ceyda Oğuz; Gaurav Singh; Gita Taherkhani
Pages: 459  473
Abstract: Abstract Port terminals processing large cargo vessels play an important role in bulk material supply chains. This paper addresses the question of how to allocate vessels to a location on a berth and the sequence in which the vessels should be processed in order to minimize delays. An important consideration in the berth allocation is the presence of tidal constraints that limit the departure of fully loaded vessels from the terminal. We show how the berth allocation problem can be modeled as an integer program and discuss a number of ways to tighten the formulation in order to make it computationally tractable. In addition, a twophase method is developed for solving these problems. Empirical computational results demonstrate an order of magnitude improvement in performance. The two new approaches can solve significantly larger instances, producing faster solutions for small instances and much tighter bounds for large instances.
PubDate: 20171001
DOI: 10.1007/s1095101705108
Issue No: Vol. 20, No. 5 (2017)
 Authors: Andreas T. Ernst; Ceyda Oğuz; Gaurav Singh; Gita Taherkhani
 Finding an optimal Nash equilibrium to the multiagent project scheduling
problem Authors: Cyril Briand; Sandra Ulrich Ngueveu; Přemysl Šůcha
Pages: 475  491
Abstract: Abstract Large projects often involve a set of contractors, each in charge of a part of the project. In this paper, we assume that every contractor is selfinterested and can control the duration of his/her activities, which can be shortened up to an incompressible limit, by gathering extra resources at a given cost. In this context, the resulting project makespan depends on all the contractors’ decisions. The customer of the project is interested in a short project makespan and offers a reward, proportional to the project makespan reduction, to be shared by the contractors. In practice, either the reward sharing policy results from an upfront agreement or payments are freely allocated by the customer. Each contractor is only interested in the maximization of his/her profit and behaves accordingly. This paper addresses the problem of finding a Nash equilibrium and a sharing policy that minimize the project makespan. The aim is to help the customer to determine the duration of the activities and the reward sharing policy such that no agent has an incentive to unilaterally deviate from this solution. We show that this problem is NPhard and how it can be modeled and solved by mixed integer linear programming. Computational analysis on large instances proves the effectiveness of our approach. Based on an empirical investigation of the influence of reward sharing policies on the project makespan, the paper provides new insight into how a project’s customer should offer rewards to the contractors.
PubDate: 20171001
DOI: 10.1007/s1095101705162
Issue No: Vol. 20, No. 5 (2017)
 Authors: Cyril Briand; Sandra Ulrich Ngueveu; Přemysl Šůcha
 Scheduling cleaning activities on trains by minimizing idle times
 Authors: Enrico Bartolini; Mauro Dell’Amico; Manuel Iori
Pages: 493  506
Abstract: Abstract We consider a workforce scheduling problem which consists of determining optimal working shifts for cleaning personnel at a rail station. Trains arrive and depart according to a specified schedule and require a given amount of cleaning time from the personnel before their departure from the station. Working shifts must specify a sequence of trains to be cleaned by a worker together with corresponding cleaning times and are subject to contract regulations which impose both a minimum and a maximum duration of the shift. We model the problem as a mixedinteger program with a pseudopolynomial number of variables and propose an exponentially sized reformulation obtained through Dantzig–Wolfe reformulation. The reformulation is strengthened by valid inequalities and used to compute lower bounds on the optimal cost. A heuristic algorithm based on column generation and variable fixing is then proposed and computationally evaluated on both a set of instances derived from real data and a larger set of randomly generated ones. The reported computational results show that the algorithm provides solutions very close to the optimal ones within 1 h of computing time.
PubDate: 20171001
DOI: 10.1007/s1095101705171
Issue No: Vol. 20, No. 5 (2017)
 Authors: Enrico Bartolini; Mauro Dell’Amico; Manuel Iori
 Crane scheduling in railway yards: an analysis of computational complexity
 Authors: Konrad Stephan; Nils Boysen
Pages: 507  526
Abstract: Abstract An efficient container transfer in railway yards is an important matter to increase the attraction of railbound freight transport. Therefore, the scheduling of gantry cranes transferring containers between freight trains and trucks or among trains received a lot of attention in the recent years. This paper contributes to this stream of research by investigating the computational complexity of crane scheduling in these yards. Scheduling the transfer of a given set of containers by a single crane equals the (asymmetric) traveling salesman problem in its pathversion. In railway yards, however, all container positions are located along parallel lines, i.e., tracks, and we face special distance metrics, so that only specially structured problem instances arise. We classify important problem settings by differentiating the transshipment direction, parking policy, and distance metric. This way, we derive problem variants being solvable to optimality in polynomial time, whereas other cases are shown to be NPhard.
PubDate: 20171001
DOI: 10.1007/s1095101705206
Issue No: Vol. 20, No. 5 (2017)
 Authors: Konrad Stephan; Nils Boysen
 Twoagent flowshop scheduling to maximize the weighted number of
justintime jobs Authors: Yunqiang Yin; T. C. E. Cheng; DuJuan Wang; ChinChia Wu
Pages: 313  335
Abstract: Abstract We consider the scheduling problem in which two agents (agents A and B), each having its own job set (containing the Ajobs and Bjobs, respectively), compete to process their own jobs in a twomachine flowshop. Each agent wants to maximize a certain criterion depending on the completion times of its jobs only. Specifically, agent A desires to maximize either the weighted number of justintime (JIT) Ajobs that are completed exactly on their due dates or the maximum weight of the JIT Ajobs, while agent B wishes to maximize the weighted number of JIT Bjobs. Evidently four optimization problems can be formulated by treating the two agents’ criteria as objectives and constraints of the corresponding optimization problems. We focus on the problem of finding the Paretooptimal schedules and present a bicriterion analysis of the problem. Solving this problem also solves the other three problems of bicriterion scheduling as a byproduct. We show that the problems under consideration are either polynomially or pseudopolynomially solvable. In addition, for each pseudopolynomialtime solution algorithm, we show how to convert it into a twodimensional fully polynomialtime approximation scheme for determining an approximate Paretooptimal schedule. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms.
PubDate: 20170801
DOI: 10.1007/s1095101705117
Issue No: Vol. 20, No. 4 (2017)
 Authors: Yunqiang Yin; T. C. E. Cheng; DuJuan Wang; ChinChia Wu
 Nonpreemptive buffer management for latency sensitive packets
 Authors: Moran Feldman; Joseph (Seffi) Naor
Pages: 337  353
Abstract: Abstract The delivery of latency sensitive packets is a crucial issue in realtime applications of communication networks. Such packets often have a firm deadline and a packet becomes useless if it arrives after its deadline. The deadline, however, applies only to the packet’s journey through the entire network; individual routers along the packet’s route face a more flexible deadline. We study policies for admitting latency sensitive packets at a router. Each packet is tagged with a value. A packet waiting at a router loses value over time as its probability of arriving at its destination on time decreases. The router is modeled as a nonpreemptive queue, and its objective is to maximize the total value of the forwarded packets. When a router receives a packet, it must either accept it (and delay future packets), or reject it immediately. The best policy depends on the set of values that a packet can take. We consider three natural sets: an unrestricted model, a realvalued model, where any value over 1 is allowed, and an integralvalued model. For the unrestricted model, we prove that there is no constant competitive ratio algorithm. For the realvalued model, we give a randomized 4competitive algorithm and a matching lower bound (up to low order terms). We also provide a deterministic lower bound of \(\phi ^3  {\varepsilon }\approx 4.236\) , almost matching the previously known 4.24competitive algorithm. For the integralvalued model, we describe a deterministic 4competitive algorithm, and prove that this is tight even for randomized algorithms (up to low order terms).
PubDate: 20170801
DOI: 10.1007/s1095101604740
Issue No: Vol. 20, No. 4 (2017)
 Authors: Moran Feldman; Joseph (Seffi) Naor
 An exact algorithm for parallel machine scheduling with conflicts
 Authors: Daniel Kowalczyk; Roel Leus
Pages: 355  372
Abstract: Abstract We consider an extension of classic parallel machine scheduling where a set of jobs is scheduled on identical parallel machines and an undirected conflict graph is part of the input. Each node in the graph represents a job, and an edge implies that its two jobs are conflicting, meaning that they cannot be scheduled on the same machine. The goal is to find an assignment of the jobs to the machines such that the maximum completion time (makespan) is minimized. We present an exact algorithm based on branch and price that combines methods from bin packing, scheduling, and graph coloring, with appropriate modifications. The algorithm has a good computational performance even for parallel machine scheduling without conflicting jobs.
PubDate: 20170801
DOI: 10.1007/s1095101604820
Issue No: Vol. 20, No. 4 (2017)
 Authors: Daniel Kowalczyk; Roel Leus
 An exact extended formulation for the unrelated parallel machine total
weighted completion time problem Authors: Kerem Bülbül; Halil Şen
Pages: 373  389
Abstract: Abstract The plethora of research on \(\mathcal {NP}\) hard parallel machine scheduling problems is focused on heuristics due to the theoretically and practically challenging nature of these problems. Only a handful of exact approaches are available in the literature, and most of these suffer from scalability issues. Moreover, the majority of the papers on the subject are restricted to the identical parallel machine scheduling environment. In this context, the main contribution of this work is to recognize and prove that a particular preemptive relaxation for the problem of minimizing the total weighted completion time (TWCT) on a set of unrelated parallel machines naturally admits a nonpreemptive optimal solution and gives rise to an exact mixed integer linear programming formulation of the problem. Furthermore, we exploit the structural properties of TWCT and attain a very fast and scalable exact Benders decompositionbased algorithm for solving this formulation. Computationally, our approach holds great promise and may even be embedded into iterative algorithms for more complex shop scheduling problems as instances with up to 1000 jobs and 8 machines are solved to optimality within a few seconds.
PubDate: 20170801
DOI: 10.1007/s109510160485x
Issue No: Vol. 20, No. 4 (2017)
 Authors: Kerem Bülbül; Halil Şen
 An implicit model for multiactivity shift scheduling problems
 Authors: Sana Dahmen; Monia Rekik; François Soumis
Abstract: Abstract We consider a multiactivity shift scheduling problem where the objective is to construct anonymous multiactivity shifts that respect union rules, satisfy the demand and minimize workforce costs. An implicit approach using adapted forward and backward constraints is proposed that integrates both the shift construction and the activity assignment problems. Our computational study shows that using the branchandbound procedure of CPLEX 12.6 on the proposed implicit model yields optimal solutions in relatively short times for environments including up to 2970 millions of explicit shifts. Our implicit model is compared to the grammarbased implicit model proposed by Côté et al. (Manag Sci 57(1):151–163, 2011b) on a large set of instances. The results prove that both implicit models have their strengths and weaknesses and are more or less efficient depending on the scheduling environment.
PubDate: 20171011
DOI: 10.1007/s109510170544y
 Authors: Sana Dahmen; Monia Rekik; François Soumis
 Singlemachine scheduling with workloaddependent tool change durations
and equal processing time jobs to minimize total completion time Authors: Zhijun Xu; Dehua Xu
Abstract: Abstract We consider a singlemachine tool change scheduling problem where tool change durations are workloaddependent. The processing times of all the jobs are the same. The objective is to determine the number of tool change activities, the start time and the completion time of each tool change activity jointly and schedule all the jobs to the machine such that the total completion time of the jobs is minimized. For the case where the tool change duration function is concave, we present a linear time optimal algorithm. For the case where the tool change duration function is convex, we convert it into a convex integer quadratic programming problem with fixed dimension and then propose two polynomial time algorithms for it. We also study some special cases for which optimal schedules can be obtained directly. For the case where the tool change duration function is linear, we present all the optimal schedules.
PubDate: 20171005
DOI: 10.1007/s109510170543z
 Authors: Zhijun Xu; Dehua Xu
 Twostage hybrid flowshop scheduling with simultaneous processing machines
 Authors: Bailin Wang; Kai Huang; Tieke Li
Abstract: Abstract Simultaneous processing machines, common in processing industries such as steel and food production, can process several jobs simultaneously in the firstin, firstout manner. However, they are often highly energyconsuming. In this paper, we study a new twostage hybrid flowshop scheduling problem, with simultaneous processing machines at the first stage and a single noidle machine with predetermined job sequence at the second stage. A mixed integer programming model is proposed with the objective of minimizing the total processing time to reduce energy consumption and improve production efficiency. We give a sufficient and necessary condition to construct feasible sequencing solutions and present an effective approach to calculate the time variables for a feasible sequencing solution. Based on these results, we design a list scheduling heuristic algorithm and its improvement. Both heuristics can find an optimal solution under certain conditions with complexity O(nlogn), where n is the number of jobs. Our experiments verify the efficiency of these heuristics compared with classical heuristics in the literature and investigate the impacts of problem size and processing times.
PubDate: 20171004
DOI: 10.1007/s109510170545x
 Authors: Bailin Wang; Kai Huang; Tieke Li
 Integrated production and outbound distribution scheduling problems with
job release dates and deadlines Authors: LiangLiang Fu; Mohamed Ali Aloulou; Christian Artigues
Abstract: Abstract In this paper, we study an integrated production and outbound distribution scheduling model with one manufacturer and one customer. The manufacturer has to process a set of jobs on a single machine and deliver them in batches to the customer. Each job has a release date and a delivery deadline. The objective of the problem is to issue a feasible integrated production and distribution schedule minimizing the transportation cost subject to the production release dates and delivery deadline constraints. We consider three problems with different ways how a job can be produced and delivered: nonsplittable production and delivery (NSP–NSD) problem, splittable production and nonsplittable delivery problem and splittable production and delivery problem. We provide polynomialtime algorithms that solve special cases of the problem. One of these algorithms allows us to compute a lower bound for the NPhard problem NSP–NSD, which we use in a branchandbound (B&B) algorithm to solve problem NSP–NSD. The computational results show that the B&B algorithm outperforms a MILP formulation of the problem implemented on a commercial solver.
PubDate: 20171004
DOI: 10.1007/s1095101705420
 Authors: LiangLiang Fu; Mohamed Ali Aloulou; Christian Artigues
 Complexity results for an integrated single machine scheduling and
outbound delivery problem with fixed sequence Abstract: Abstract In this paper, we consider an integrated production and outbound delivery scheduling problem. In particular, we address the situation in which the scheduling sequence and the delivery sequence are the same and predefined. A set of jobs are processed on a single machine, and finished jobs are delivered to the customers by a single capacitated vehicle. Each job has a processing time, and transportation times between customers are taken into account. Because the sequence is given, the problem consists in forming batches of jobs and our objective is to minimize the sum of the delivery times or general functions of the delivery times. The NPhardness of the general problem is established, and a pseudopolynomial time dynamic programming algorithm is given. Some particular cases are treated, for which NPhardness proofs and polynomial time algorithms are given. Finally, a fixedparameter tractability result is given.
PubDate: 20170908
DOI: 10.1007/s1095101705402
 Abstract: Abstract In this paper, we consider an integrated production and outbound delivery scheduling problem. In particular, we address the situation in which the scheduling sequence and the delivery sequence are the same and predefined. A set of jobs are processed on a single machine, and finished jobs are delivered to the customers by a single capacitated vehicle. Each job has a processing time, and transportation times between customers are taken into account. Because the sequence is given, the problem consists in forming batches of jobs and our objective is to minimize the sum of the delivery times or general functions of the delivery times. The NPhardness of the general problem is established, and a pseudopolynomial time dynamic programming algorithm is given. Some particular cases are treated, for which NPhardness proofs and polynomial time algorithms are given. Finally, a fixedparameter tractability result is given.
 Fault tolerant scheduling of tasks of two sizes under resource
augmentation Abstract: Abstract Guaranteeing the eventual execution of tasks in machines that are prone to unpredictable crashes and restarts may be challenging, but is also of high importance. Things become even more complicated when tasks arrive dynamically and have different computational demands, i.e., processing time (or sizes). In this paper, we focus on the online task scheduling in such systems, considering one machine and at least two different task sizes. More specifically, algorithms are designed for two different task sizes while the complementary bounds hold for any number of task sizes bigger than one. We look at the latency and 1completed load competitiveness properties of deterministic scheduling algorithms under worstcase scenarios. For this, we assume an adversary, that controls the machine crashes and restarts as well as the task arrivals of the system, including their computational demands. More precisely, we investigate the effect of resource augmentation—in the form of processor speedup—in the machine’s performance, by looking at the two efficiency measures for different speedups. We first identify the threshold of the speedup under which competitiveness cannot be achieved by any deterministic algorithm, and above which there exists some deterministic algorithm that is competitive. We then propose an online algorithm, named \(\gamma \text{Burst } \) , that achieves both latency and 1completedload competitiveness when the speedup is over the threshold. This also proves that the threshold identified is also sufficient for competitiveness.
PubDate: 20170907
DOI: 10.1007/s1095101705411
 Abstract: Abstract Guaranteeing the eventual execution of tasks in machines that are prone to unpredictable crashes and restarts may be challenging, but is also of high importance. Things become even more complicated when tasks arrive dynamically and have different computational demands, i.e., processing time (or sizes). In this paper, we focus on the online task scheduling in such systems, considering one machine and at least two different task sizes. More specifically, algorithms are designed for two different task sizes while the complementary bounds hold for any number of task sizes bigger than one. We look at the latency and 1completed load competitiveness properties of deterministic scheduling algorithms under worstcase scenarios. For this, we assume an adversary, that controls the machine crashes and restarts as well as the task arrivals of the system, including their computational demands. More precisely, we investigate the effect of resource augmentation—in the form of processor speedup—in the machine’s performance, by looking at the two efficiency measures for different speedups. We first identify the threshold of the speedup under which competitiveness cannot be achieved by any deterministic algorithm, and above which there exists some deterministic algorithm that is competitive. We then propose an online algorithm, named \(\gamma \text{Burst } \) , that achieves both latency and 1completedload competitiveness when the speedup is over the threshold. This also proves that the threshold identified is also sufficient for competitiveness.
 Case mix classification and a benchmark set for surgery scheduling
 Authors: Gréanne Leeftink; Erwin W. Hans
Abstract: Abstract Numerous benchmark sets exist for combinatorial optimization problems. However, in healthcare scheduling, only a few benchmark sets are known, mainly focused on nurse rostering. One of the most studied topics in the healthcare scheduling literature is surgery scheduling, for which there is no widely used benchmark set. An effective benchmark set should be diverse, reflect the real world, contain large instances, and be extendable. This paper proposes a benchmark set for surgery scheduling algorithms, which satisfies these four criteria. Surgery scheduling instances are characterized by an underlying case mix, which describes the volume and properties of the surgery types. Given a case mix, unlimited random instances can be generated. A complete surgery scheduling benchmark set should encompass the diversity of prevalent case mixes. We therefore propose a case mix classification scheme, which we use to typify both reallife and theoretical case mixes that span the breadth of possible case mix types. Our full benchmark set contains 20,880 instances, with a small benchmark subset of 146 instances. The instances are generated based on reallife case mixes (11 surgical specialties), as well as theoretical instances. The instances were generated using a novel instance generation procedure, which introduces the concept of “instance proximity” to measure the similarity between two instances, and which uses this concept to generate sets of instances that are as diverse as possible.
PubDate: 20170905
DOI: 10.1007/s1095101705398
 Authors: Gréanne Leeftink; Erwin W. Hans
 Scheduling electric vehicles and locating charging stations on a path
 Authors: Nils Boysen; Dirk Briskorn; Simon Emde
Abstract: Abstract High hopes are put in electric vehicles to lower global green house gas emissions. From an operational perspective, however, their limited range and the long recharging times add considerable complexity to the decision tasks planning their efficient application. In this context, we treat a problem setting where a single electric vehicle executes transport requests along a straight line, which, for instance, occurs when cranes, automated guided vehicles, or shuttles handle boxes in container terminals. From time to time the vehicle needs to be recharged and, thus, has to visit some charging station also located on the line. We investigate the scheduling of a single electric vehicle, so that the makespan for executing all transport requests is minimized and the vehicle is timely recharged. The solution algorithm developed is then applied to also explore the location planning of charging stations.
PubDate: 20170824
DOI: 10.1007/s1095101705389
 Authors: Nils Boysen; Dirk Briskorn; Simon Emde
 Offline firstfit decreasing height scheduling of power loads
 Authors: Anshu Ranjan; Pramod Khargonekar; Sartaj Sahni
Abstract: Abstract In this paper, we consider the problem of scheduling energy consumption loads in the setting of smart electric grids. Each load is characterized as a “job” by a start (arrival) time and a deadline by which a certain amount of electric energy must be delivered to the load. A job may be preemptable, i. e. it can be interrupted or nonpreemptable. Specifically, we focus on scheduling a mixture of preemptable and nonpreemptable jobs with the same arrival time and deadline with the goal of minimizing the peak power. We study and modify the firstfit decreasing height algorithm of the strip packing problem for this purpose. We prove its asymptotic performance bound: \(1.7 OPT + 1\) and its tightness. The heuristic results in at most one preemption per job, and it can be implemented with \(O(n \log n + nq)\) time complexity where q is the number of \(nonpreemptable\) jobs.
PubDate: 20170621
DOI: 10.1007/s109510170528y
 Authors: Anshu Ranjan; Pramod Khargonekar; Sartaj Sahni
 A neighborhood for complex job shop scheduling problems with regular
objectives Authors: Reinhard Bürgy
Abstract: Abstract Due to the limited applicability in practice of the classical job shop scheduling problem, many researchers have addressed more complex versions of this problem by including additional process features, such as time lags, setup times, and buffer limitations, and have pursued objectives that are more practically relevant than the makespan, such as total flow time and total weighted tardiness. However, most proposed solution approaches are tailored to the specific scheduling problem studied and are not applicable to more general settings. This article proposes a neighborhood that can be applied for a large class of job shop scheduling problems with regular objectives. Feasible neighbor solutions are generated by extracting a job from a given solution and reinserting it into a neighbor position. This neighbor generation in a sense extends the simple swapping of critical arcs, a mechanism that is widely used in the classical job shop but that is not applicable in more complex job shop problems. The neighborhood is embedded in a tabu search, and its performance is evaluated with an extensive experimental study using three standard job shop scheduling problems: the (classical) job shop, the job shop with sequencedependent setup times, and the blocking job shop, combined with the following five regular objectives: makespan, total flow time, total squared flow time, total tardiness, and total weighted tardiness. The obtained results support the validity of the approach.
PubDate: 20170614
DOI: 10.1007/s1095101705322
 Authors: Reinhard Bürgy