
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 [2345 journals] 
 Continuoustime production, distribution and financial planning with
periodic liquidity balancing Authors: Wolfgang Albrecht; Martin Steinrücke
Pages: 219  237
Abstract: Due to the inevitable focus on core competencies, even small and mediumsized companies are increasingly forced to form supply chain (SC) networks. However, their specific situation is often characterized by a lack of equity and limited access to capital markets, so that bank loans must then be used to initiate production and distribution. Within a shortterm multiday planning horizon, both operations and finance must be scheduled precisely in order to obtain practical instructions for each network partner and the network managers. For this purpose, continuoustime modeling is required. Additionally, a coordination of monetary consequences resulting from both sitespecific operational events and networkwide financial transactions is necessary to prevent insolvency. As bank overdrafts can be used to overcome financial imbalances during short periods (e.g., days or even hours), appropriate time intervals for liquidity management should be determined. The implementation of these intervals requires discretetime modeling. In this context, the main challenge is to combine both of the aforementioned modeling techniques within a common decision model. To address this problem, a novel mixedinteger nonlinear program (MINLP) is developed, which enables exact planning and scheduling of SC operations as well as related financial transactions on the one hand, and periodic liquidity balancing on the other hand. A numerical analysis was based on a test scenario with randomly generated data. As we found out that even small problem instances of the MINLP, e.g., a threestage supply chain with three sites in each stage, were not computable with highperformance hardware and a commercial nonlinear standard solver, we additionally propose an equivalent linearized version of the decision model. The latter could be optimized within acceptable computation time using the CPLEX solver.
PubDate: 20170601
DOI: 10.1007/s1095101604887
Issue No: Vol. 20, No. 3 (2017)
 Authors: Wolfgang Albrecht; Martin Steinrücke
 The local–global conjecture for scheduling with nonlinear cost
 Authors: Nikhil Bansal; Christoph Dürr; Nguyen Kim Thang; Óscar C. Vásquez
Pages: 239  254
Abstract: We consider the classical scheduling problem on a single machine, on which we need to schedule sequentially n given jobs. Every job j has a processing time \(p_j\) and a priority weight \(w_j\) , and for a given schedule a completion time \(C_j\) . In this paper, we consider the problem of minimizing the objective value \(\sum _j w_j C_j^\beta \) for some fixed constant \(\beta >0\) . This nonlinearity is motivated for example by the learning effect of a machine improving its efficiency over time, or by the speed scaling model. For \(\beta =1\) , the wellknown Smith’s rule that orders job in the nonincreasing order of \(w_j/p_j\) gives the optimum schedule. However, for \(\beta \ne 1\) , the complexity status of this problem is open. Among other things, a key issue here is that the ordering between a pair of jobs is not well defined, and might depend on where the jobs lie in the schedule and also on the jobs between them. We investigate this question systematically and substantially generalize the previously known results in this direction. These results lead to interesting new dominance properties among schedules which lead to huge speed up in exact algorithms for the problem. An experimental study evaluates the impact of these properties on the exact algorithm A*.
PubDate: 20170601
DOI: 10.1007/s1095101504665
Issue No: Vol. 20, No. 3 (2017)
 Authors: Nikhil Bansal; Christoph Dürr; Nguyen Kim Thang; Óscar C. Vásquez
 A parameterized complexity view on nonpreemptively scheduling
 Authors: René van Bevern; Rolf Niedermeier; Ondřej Suchý
Pages: 255  265
Abstract: We study the problem of nonpreemptively scheduling n jobs, each job j with a release time \(t_j\) , a deadline \(d_j\) , and a processing time \(p_j\) , on m parallel identical machines. Cieliebak et al. (2004) considered the two constraints \( d_jt_j \le \lambda {}p_j\) and \( d_jt_j \le p_j +\sigma \) and showed the problem to be NPhard for any \(\lambda >1\) and for any \(\sigma \ge 2\) . We complement their results by parameterized complexity studies: we show that, for any \(\lambda >1\) , the problem remains weakly NPhard even for \(m=2\) and strongly W[1]hard parameterized by m. We present a pseudopolynomialtime algorithm for constant m and \(\lambda \) and a fixedparameter tractability result for the parameter m combined with \(\sigma \) .
PubDate: 20170601
DOI: 10.1007/s1095101604789
Issue No: Vol. 20, No. 3 (2017)
 Authors: René van Bevern; Rolf Niedermeier; Ondřej Suchý
 Optimal scheduling of contract algorithms with soft deadlines
 Authors: Spyros Angelopoulos; Alejandro LópezOrtiz; Angèle Hamel
Pages: 267  277
Abstract: A contract algorithm is an algorithm which is given, as part of its input, a specified amount of allowable computation time, and may not return useful results if interrupted prior to that time. In contrast, an interruptible algorithm will always output some meaningful (albeit suboptimal) solution, even if interrupted during its execution. Simulating interruptible algorithms by means of schedules of executions of contract algorithms in parallel processors is a wellstudied problem with significant applications in AI. In the standard model, the interruptions are hard deadlines in which a solution must be reported immediately at the time the interruption occurs. In this paper, we study the more general setting of scheduling contract algorithms in the presence of soft deadlines. In particular, we address the setting in which if an interruption occurs at time t, then the system is given an additional window of time \(w(t)\le c \cdot t\) , for constant c, within which the simulation must be completed. We formulate extensions to performance measures of schedules under this setting and derive schedules of optimal performance for all concave functions w.
PubDate: 20170601
DOI: 10.1007/s109510160483z
Issue No: Vol. 20, No. 3 (2017)
 Authors: Spyros Angelopoulos; Alejandro LópezOrtiz; Angèle Hamel
 A greedy approximation algorithm for minimumgap scheduling
 Authors: Marek Chrobak; Uriel Feige; Mohammad Taghi Hajiaghayi; Sanjeev Khanna; Fei Li; Seffi Naor
Pages: 279  292
Abstract: We consider scheduling of unitlength jobs with release times and deadlines, where the objective is to minimize the number of gaps in the schedule. Polynomialtime algorithms for this problem are known, yet they are rather inefficient, with the best algorithm running in time \(O(n^4)\) and requiring \(O(n^3)\) memory. We present a greedy algorithm that approximates the optimum solution within a factor of 2 and show that our analysis is tight. Our algorithm runs in time \(O(n^2 \log n)\) and needs only O(n) memory. In fact, the running time is \(O(n (g^*+1)\log n)\) , where \(g^*\) is the minimum number of gaps.
PubDate: 20170601
DOI: 10.1007/s109510160492y
Issue No: Vol. 20, No. 3 (2017)
 Authors: Marek Chrobak; Uriel Feige; Mohammad Taghi Hajiaghayi; Sanjeev Khanna; Fei Li; Seffi Naor
 Twomachine flowshop scheduling with threeoperation jobs subject to a
fixed job sequence Authors: Bertrand M. T. Lin; F. J. Hwang; Jatinder N. D. Gupta
Pages: 293  302
Abstract: This paper studies the problem of scheduling threeoperation jobs in a twomachine flowshop subject to a predetermined job processing sequence. Each job has two preassigned operations, which are to be performed on their respective dedicated machines, and a flexible operation, which may be processed on either of the two machines subject to the processing order as specified. Five standard objective functions, including the makespan, the maximum lateness, the total weighted completion time, the total weighted tardiness, and the weighted number of tardy jobs are considered. We show that the studied problem for either of the five considered objective functions is ordinary NPhard, even if the processing times of the preassigned operations are zero for all jobs. A pseudopolynomial time dynamic programming framework, coupled with brief numerical experiments, is then developed for all the addressed performance metrics with different run times.
PubDate: 20170601
DOI: 10.1007/s109510160493x
Issue No: Vol. 20, No. 3 (2017)
 Authors: Bertrand M. T. Lin; F. J. Hwang; Jatinder N. D. Gupta
 Offline firstfit decreasing height scheduling of power loads
 Authors: Anshu Ranjan; Pramod Khargonekar; Sartaj Sahni
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: 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
 Discovering dispatching rules from data using imitation learning: A case
study for the jobshop problem Authors: Helga Ingimundardottir; Thomas Philip Runarsson
Abstract: Dispatching rules can be automatically generated from scheduling data. This paper will demonstrate that the key to learning an effective dispatching rule is through the careful construction of the training data, \(\{\mathbf {x}_i(k),y_i(k)\}_{k=1}^K\in {\mathscr {D}}\) , where (i) features of partially constructed schedules \(\mathbf {x}_i\) should necessarily reflect the induced data distribution \({\mathscr {D}}\) for when the rule is applied. This is achieved by updating the learned model in an active imitation learning fashion; (ii) \(y_i\) is labelled optimally using a MIP solver; and (iii) data need to be balanced, as the set is unbalanced with respect to the dispatching step k. Using the guidelines set by our framework the design of custom dispatching rules, for a particular scheduling application, will become more effective. In the study presented three different distributions of the jobshop will be considered. The machine learning approach considered is based on preference learning, i.e. which dispatch (postdecision state) is preferable to another.
PubDate: 20170613
DOI: 10.1007/s1095101705340
 Authors: Helga Ingimundardottir; Thomas Philip Runarsson
 A hybrid scheduling approach for a twostage flexible flow shop with batch
processing machines Authors: Yi Tan; Lars Mönch; John W. Fowler
Abstract: In this paper, we discuss a flexible flow shop scheduling problem with batch processing machines at each stage and with jobs that have unequal ready times. Scheduling problems of this type can be found in semiconductor wafer fabrication facilities (wafer fabs). We are interested in minimizing the total weighted tardiness of the jobs. We present a mixed integer programming formulation. The batch scheduling problem is NPhard. Therefore, an iterative stagebased decomposition approach is proposed that is hybridized with neighborhood search techniques. The decomposition scheme provides internal due dates and ready times for the jobs on the first and second stage, respectively. Each of the resulting parallel machine batch scheduling problems is solved by variable neighborhood search in each iteration. Based on the schedules of the subproblems, the internal due dates and ready times are updated. We present the results of designed computational experiments that also consider the number of machines assigned to each stage as a design factor. It turns out that the proposed hybrid approach outperforms an iterative decomposition scheme where a fairly simple heuristic based on time window decomposition and the apparent tardiness cost dispatching rule is used to solve the subproblems. Recommendations for the design of the two stages with respect to the number of parallel machines on each stage are given.
PubDate: 20170613
DOI: 10.1007/s1095101705304
 Authors: Yi Tan; Lars Mönch; John W. Fowler
 LP rounding and combinatorial algorithms for minimizing active and busy
time Authors: Jessica Chang; Samir Khuller; Koyel Mukherjee
Abstract: We consider fundamental scheduling problems motivated by energy issues. In this framework, we are given a set of jobs, each with a release time, deadline, and required processing length. The jobs need to be scheduled on a machine so that at most g jobs are active at any given time. The duration for which a machine is active (i.e., “on”) is referred to as its active time. The goal is to find a feasible schedule for all jobs, minimizing the total active time. When preemption is allowed at integer time points, we show that a minimal feasible schedule already yields a 3approximation (and this bound is tight) and we further improve this to a 2approximation via LP rounding techniques. Our second contribution is for the nonpreemptive version of this problem. However, since even asking if a feasible schedule on one machine exists is NPhard, we allow for an unbounded number of virtual machines, each having capacity of g. This problem is known as the busy time problem in the literature and a 4approximation is known for this problem. We develop a new combinatorial algorithm that gives a 3approximation. Furthermore, we consider the preemptive busy time problem, giving a simple and exact greedy algorithm when unbounded parallelism is allowed, i.e., g is unbounded. For arbitrary g, this yields an algorithm that is 2approximate.
PubDate: 20170610
DOI: 10.1007/s1095101705313
 Authors: Jessica Chang; Samir Khuller; Koyel Mukherjee
 Family scheduling with batch availability in flow shops to minimize
makespan Authors: Liji Shen; Jatinder N. D. Gupta
Abstract: This paper addresses a batch scheduling problem in flow shop production systems, where job families are formed based on setup similarities. In order to improve setup efficiency, we consider batching decisions in our solution procedure. Due to its high practical relevance, the batch availability assumption is also adopted in this study. In the presence of sequencedependent setup times, it is proved that a permutation flow shop is generally not optimal. Therefore, our objective is to determine solutions with inconsistent batches, which essentially lead to nonpermutation schedules, to minimize makespan. After examining structural properties, we develop a tabu search algorithm with multiple neighbourhood functions. Computational results confirm the remarkable benefits of batching decisions. Our algorithm also outperforms some wellknown and wellperforming approaches.
PubDate: 20170522
DOI: 10.1007/s109510170529x
 Authors: Liji Shen; Jatinder N. D. Gupta
 The triangle scheduling problem
 Authors: Christoph Dürr; Zdeněk Hanzálek; Christian Konrad; Yasmina Seddik; René Sitters; Óscar C. Vásquez; Gerhard Woeginger
Abstract: This paper introduces a novel scheduling problem, where jobs occupy a triangular shape on the time line. This problem is motivated by scheduling jobs with different criticality levels. A measure is introduced, namely the binary tree ratio. It is shown that the Greedy algorithm solves the problem to optimality when the binary tree ratio of the input instance is at most 2. We also show that the problem is unary NPhard for instances with binary tree ratio strictly larger than 2 and provide a quasipolynomial time approximation scheme. The approximation ratio of Greedy on general instances is shown to be between 1.5 and 1.05.
PubDate: 20170518
DOI: 10.1007/s1095101705331
 Authors: Christoph Dürr; Zdeněk Hanzálek; Christian Konrad; Yasmina Seddik; René Sitters; Óscar C. Vásquez; Gerhard Woeginger
 A survey on how the structure of precedence constraints may change the
complexity class of scheduling problems Authors: D. Prot; O. BellenguezMorineau
Abstract: This survey aims to demonstrate that the structure of precedence constraints plays a tremendous role on the complexity of scheduling problems. Indeed, many problems can be \(\mathcal {NP}\) hard when considering general precedence constraints, while they become polynomially solvable for particular precedence constraints. Additionally, the existence of many very exciting challenges in this research area is underlined.
PubDate: 20170508
DOI: 10.1007/s109510170519z
 Authors: D. Prot; O. BellenguezMorineau
 Staff and machine shift scheduling in a German potash mine
 Authors: Marco Schulze; Jürgen Zimmermann
Abstract: This paper addresses a shortterm production scheduling problem that arises in a German potash underground mine. In particular, we consider a combined staff and machine scheduling problem where mining operations have to be assigned to resources and scheduled simultaneously. The resources are composed of the machines and workers that are available in the upcoming working shift. Due to the given application, several miningspecific requirements have to be taken into account, e.g., how to handle mining operations within the same underground location. In order to solve the problem, we propose a construction procedure that is extended to a multistart algorithm. In a computational study, we conduct experiments on random as well as realworld instances.
PubDate: 20170429
DOI: 10.1007/s109510170527z
 Authors: Marco Schulze; Jürgen Zimmermann
 A listscheduling heuristic for the shortterm planning of assessment
centers Authors: Adrian Zimmermann; Norbert Trautmann
Abstract: Many companies operate assessment centers to help them select candidates for open job positions. During the assessment process, each candidate performs a set of tasks, and the candidates are evaluated by some socalled assessors. Additional constraints such as preparation and evaluation times, actors’ participation in tasks, nogo relationships, and prescribed time windows for lunch breaks contribute to the complexity of planning such assessment processes. We propose a multipass listscheduling heuristic for this novel planning problem; to this end, we develop novel procedures for devising appropriate scheduling lists and for generating a feasible schedule. The computational results for a set of example problems that represent or are derived from real cases indicate that the heuristic generates optimal or nearoptimal schedules within relatively short CPU times.
PubDate: 20170427
DOI: 10.1007/s1095101705215
 Authors: Adrian Zimmermann; Norbert Trautmann
 Exact exponential algorithms for 3machine flowshop scheduling problems
 Authors: Lei Shang; Christophe Lenté; Mathieu Liedloff; Vincent T’Kindt
Abstract: In this paper, we focus on the design of an exact exponential time algorithm with a proved worstcase running time for 3machine flowshop scheduling problems considering worstcase scenarios. For the minimization of the makespan criterion, a Dynamic Programming algorithm running in \({\mathcal {O}}^*(3^n)\) is proposed, which improves the current bestknown time complexity \(2^{{\mathcal {O}}(n)}\times \Vert I\Vert ^{{\mathcal {O}}(1)}\) in the literature. The idea is based on a dominance condition and the consideration of the Pareto Front in the criteria space. The algorithm can be easily generalized to other problems that have similar structures. The generalization on two problems, namely the \(F3\Vert f_\mathrm{max}\) and \(F3\Vert \sum f_i\) problems, is discussed.
PubDate: 20170427
DOI: 10.1007/s1095101705242
 Authors: Lei Shang; Christophe Lenté; Mathieu Liedloff; Vincent T’Kindt
 Scheduling multipacket frames with frame deadlines
 Authors: Łukasz Jeż; Yishay Mansour; Boaz PattShamir
Abstract: We consider scheduling information units called frames, each with a delivery deadline. Frames consist of packets, which arrive online in a roughly periodic fashion, and compete on allocation of transmission slots. A frame is deemed useful only if all its packets are delivered before its deadline. We focus on a “proportional” variant, where the value of each frame is proportional to its size, but the sizes and periods of the frames are arbitrary. We give a constantcompetitive algorithm for this setting, assuming bounded jitter and some slack in the frames’ deadlines, the latter of which is necessary. Using standard techniques, our algorithm yields polylogcompetitive algorithms for general instances with slack and bounded jitter.
PubDate: 20170427
DOI: 10.1007/s1095101705224
 Authors: Łukasz Jeż; Yishay Mansour; Boaz PattShamir
 Crane scheduling in railway yards: an analysis of computational complexity
 Authors: Konrad Stephan; Nils Boysen
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: 20170427
DOI: 10.1007/s1095101705206
 Authors: Konrad Stephan; Nils Boysen
 The equivalence of two classical list scheduling algorithms for dependent
typed tasks with release dates, due dates and precedence delays Authors: Aurélien Carlier; Claire Hanen; Alix Munier Kordon
Abstract: We consider a finite set of unit time execution tasks with release dates, due dates and precedence delays. The machines are partitioned into k classes. Each task requires one machine from a fixed class to be executed. The problem is the existence of a feasible schedule. This general problem is known to be \(\mathcal {NP}\) complete; many studies were devoted to the determination of polynomial time algorithms for some special subcases, most of them based on a particular list schedule. The Garey–Johnson and Leung–Palem–Pnueli algorithms (respectively GJ and LPP in short) are both improving the due dates to build a priority list. They are modifying them using necessary conditions until a fixed point is reached. The present paper shows that these two algorithms are different implementations of the same generic one. The main consequence is that all the results valid for GJ algorithm are also for LPP and vice versa.
PubDate: 20170214
DOI: 10.1007/s1095101605078
 Authors: Aurélien Carlier; Claire Hanen; Alix Munier Kordon