for Journals by Title or ISSN for Articles by Keywords help
 Subjects -> COMPUTER SCIENCE (Total: 1967 journals)     - ANIMATION AND SIMULATION (29 journals)    - ARTIFICIAL INTELLIGENCE (97 journals)    - AUTOMATION AND ROBOTICS (96 journals)    - CLOUD COMPUTING AND NETWORKS (62 journals)    - COMPUTER ARCHITECTURE (9 journals)    - COMPUTER ENGINEERING (10 journals)    - COMPUTER GAMES (15 journals)    - COMPUTER PROGRAMMING (23 journals)    - COMPUTER SCIENCE (1146 journals)    - COMPUTER SECURITY (45 journals)    - DATA BASE MANAGEMENT (12 journals)    - DATA MINING (32 journals)    - E-BUSINESS (22 journals)    - E-LEARNING (28 journals)    - ELECTRONIC DATA PROCESSING (21 journals)    - IMAGE AND VIDEO PROCESSING (40 journals)    - INFORMATION SYSTEMS (100 journals)    - INTERNET (91 journals)    - SOCIAL WEB (49 journals)    - SOFTWARE (32 journals)    - THEORY OF COMPUTING (8 journals) COMPUTER SCIENCE (1146 journals)
 The end of the list has been reached or no journals were found for your choice.
 Journal of Scheduling   [SJR: 1.053]   [H-I: 47]   [5 followers]  Follow         Hybrid journal (It can contain Open Access articles)    ISSN (Print) 1099-1425 - ISSN (Online) 1094-6136    Published by Springer-Verlag  [2340 journals]
• Continuous-time production, distribution and financial planning with
periodic liquidity balancing
• Authors: Wolfgang Albrecht; Martin Steinrücke
Pages: 219 - 237
Abstract: Abstract Due to the inevitable focus on core competencies, even small- and medium-sized 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 short-term multi-day 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, continuous-time modeling is required. Additionally, a coordination of monetary consequences resulting from both site-specific operational events and network-wide 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 discrete-time 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 mixed-integer 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 three-stage supply chain with three sites in each stage, were not computable with high-performance 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: 2017-06-01
DOI: 10.1007/s10951-016-0488-7
Issue No: Vol. 20, No. 3 (2017)

• The local–global conjecture for scheduling with non-linear cost
• Authors: Nikhil Bansal; Christoph Dürr; Nguyen Kim Thang; Óscar C. Vásquez
Pages: 239 - 254
Abstract: 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 non-linearity 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 well-known Smith’s rule that orders job in the non-increasing 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: 2017-06-01
DOI: 10.1007/s10951-015-0466-5
Issue No: Vol. 20, No. 3 (2017)

• A parameterized complexity view on non-preemptively scheduling

• Authors: René van Bevern; Rolf Niedermeier; Ondřej Suchý
Pages: 255 - 265
Abstract: Abstract We study the problem of non-preemptively 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_j-t_j \le \lambda {}p_j$$ and $$d_j-t_j \le p_j +\sigma$$ and showed the problem to be NP-hard 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 NP-hard even for  $$m=2$$ and strongly W[1]-hard parameterized by m. We present a pseudo-polynomial-time algorithm for constant m and  $$\lambda$$ and a fixed-parameter tractability result for the parameter m combined with  $$\sigma$$ .
PubDate: 2017-06-01
DOI: 10.1007/s10951-016-0478-9
Issue No: Vol. 20, No. 3 (2017)

• Optimal scheduling of contract algorithms with soft deadlines
• Authors: Spyros Angelopoulos; Alejandro López-Ortiz; Angèle Hamel
Pages: 267 - 277
Abstract: 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 well-studied 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: 2017-06-01
DOI: 10.1007/s10951-016-0483-z
Issue No: Vol. 20, No. 3 (2017)

• A greedy approximation algorithm for minimum-gap scheduling
• Authors: Marek Chrobak; Uriel Feige; Mohammad Taghi Hajiaghayi; Sanjeev Khanna; Fei Li; Seffi Naor
Pages: 279 - 292
Abstract: Abstract We consider scheduling of unit-length jobs with release times and deadlines, where the objective is to minimize the number of gaps in the schedule. Polynomial-time 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: 2017-06-01
DOI: 10.1007/s10951-016-0492-y
Issue No: Vol. 20, No. 3 (2017)

• Two-machine flowshop scheduling with three-operation jobs subject to a
fixed job sequence
• Authors: Bertrand M. T. Lin; F. J. Hwang; Jatinder N. D. Gupta
Pages: 293 - 302
Abstract: Abstract This paper studies the problem of scheduling three-operation jobs in a two-machine 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 NP-hard, even if the processing times of the preassigned operations are zero for all jobs. A pseudo-polynomial time dynamic programming framework, coupled with brief numerical experiments, is then developed for all the addressed performance metrics with different run times.
PubDate: 2017-06-01
DOI: 10.1007/s10951-016-0493-x
Issue No: Vol. 20, No. 3 (2017)

• Improved approaches to the exact solution of the machine covering problem
• Authors: Rico Walter; Martin Wirth; Alexander Lawrinenko
Pages: 147 - 164
Abstract: Abstract For the basic problem of scheduling a set of n independent jobs on a set of m identical parallel machines with the objective of maximizing the minimum machine completion time—also referred to as machine covering—we propose a new exact branch-and-bound algorithm. Its most distinctive components are a different symmetry-breaking solution representation, enhanced lower and upper bounds, and effective novel dominance criteria derived from structural patterns of optimal schedules. Results of a comprehensive computational study conducted on benchmark instances attest to the effectiveness of our approach, particularly for small ratios of n to m.
PubDate: 2017-04-01
DOI: 10.1007/s10951-016-0477-x
Issue No: Vol. 20, No. 2 (2017)

• A hybrid multi-objective immune algorithm for predictive and reactive
scheduling
• Authors: Iwona Paprocka; Bożena Skołud
Pages: 165 - 182
Abstract: Abstract The high productivity of a production process has a major impact on the reduction of the production cost and on a quick response to changing demands. Information about a failure-free machine operation time obtained in advance allows the users to plan preventive maintenance in order to keep the machine in a good operational condition. The introduction of maintenance work into a schedule reduces the frequency of unpredicted breaks caused by machine failures. It also results in higher productivity and in-time production. The foregoing of this constitutes the main idea of the predictive scheduling method proposed in the paper. Rescheduling of disrupted operations, with a minimal impact on the stability and robustness of a schedule, is the main idea of the reactive scheduling method proposed. The first objective of the paper is to present a hybrid multi-objective immune algorithm (H-MOIA) aided by heuristics: a minimal impact of disrupted operation on the schedule (MIDOS) for predictive scheduling and a minimal impact of rescheduled operation on the schedule (MIROS) for reactive scheduling. The second objective is to compare the H-MOIA with various methods for predictive and reactive scheduling. The H-MOIA + MIDOS is compared to two algorithms, identified in reference publications: (1) an algorithm based on priority rules: the least flexible job first (LFJ) and the longest processing time (LPT) (2) an Average Slack Method. The H-MOIA + MIROS is compared to: (1) an algorithm based on priority rules: the LFJ and LPT and (2) Shifted Gap-Reduction. This paper presents the research results and computer simulations.
PubDate: 2017-04-01
DOI: 10.1007/s10951-016-0494-9
Issue No: Vol. 20, No. 2 (2017)

• Scheduling jobs and maintenance activities subject to job-dependent
machine deteriorations
• Authors: Liliana Grigoriu; Dirk Briskorn
Pages: 183 - 197
Abstract: Abstract This paper considers machine scheduling that integrates machine deterioration caused by jobs and, consequently, maintenance activities. The maintenance state of the machine is represented by a maintenance level which drops by a certain, possibly job-dependent amount while jobs are processed. A maintenance level of less than zero is associated with the machine’s breakdown and is therefore forbidden. Hence, maintenance activities that raise the maintenance level may become necessary and have to be scheduled additionally. We consider the objective to minimize the makespan throughout the paper. For the single machine case, we provide a linear-time approximation algorithm with worst-case a bound of 5/4, and comment on how an FPTAS from previous literature can be employed to apply to our problem. Due to problem similarity, these results also apply to the minimum subset sum problem, and the 5/4 linear-time approximation algorithm is an improvement over the 5/4 quadratic-time approximation algorithm of Güntzer and Jungnickel. For the general problem with multiple machines, we provide approximability results, two fast heuristics, an approximation algorithm with an instance-dependent approximation factor and a computational study evaluating the heuristics.
PubDate: 2017-04-01
DOI: 10.1007/s10951-016-0502-0
Issue No: Vol. 20, No. 2 (2017)

• Batched bin packing revisited
• Authors: Gyorgy Dosa
Pages: 199 - 209
Abstract: Abstract We revisit the batched bin packing problem. In this model, items come in K consecutive batches, and the items of the earlier batches must be packed without any knowledge of later batches. We give the first approximation algorithm for the case $$K=2$$ , with tight asymptotic approximation ratio of 1.5833, while the known lower bound of the model is 1.378. With the application of this result, we are also able to provide an improved algorithm for the recently defined graph-bin packing problem in a special case, where we improve the upper bound from 3 to 2.5833.
PubDate: 2017-04-01
DOI: 10.1007/s10951-015-0431-3
Issue No: Vol. 20, No. 2 (2017)

• A list-scheduling heuristic for the short-term planning of assessment
centers
• Authors: Adrian Zimmermann; Norbert Trautmann
Abstract: 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 so-called assessors. Additional constraints such as preparation and evaluation times, actors’ participation in tasks, no-go relationships, and prescribed time windows for lunch breaks contribute to the complexity of planning such assessment processes. We propose a multi-pass list-scheduling 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 near-optimal schedules within relatively short CPU times.
PubDate: 2017-04-27
DOI: 10.1007/s10951-017-0521-5

• Exact exponential algorithms for 3-machine flowshop scheduling problems
• Authors: Lei Shang; Christophe Lenté; Mathieu Liedloff; Vincent T’Kindt
Abstract: Abstract In this paper, we focus on the design of an exact exponential time algorithm with a proved worst-case running time for 3-machine flowshop scheduling problems considering worst-case scenarios. For the minimization of the makespan criterion, a Dynamic Programming algorithm running in $${\mathcal {O}}^*(3^n)$$ is proposed, which improves the current best-known 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: 2017-04-27
DOI: 10.1007/s10951-017-0524-2

• Scheduling multipacket frames with frame deadlines
• Authors: Łukasz Jeż; Yishay Mansour; Boaz Patt-Shamir
Abstract: 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 constant-competitive 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 polylog-competitive algorithms for general instances with slack and bounded jitter.
PubDate: 2017-04-27
DOI: 10.1007/s10951-017-0522-4

• Crane scheduling in railway yards: an analysis of computational complexity
• Authors: Konrad Stephan; Nils Boysen
Abstract: Abstract An efficient container transfer in railway yards is an important matter to increase the attraction of rail-bound 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 path-version. 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 NP-hard.
PubDate: 2017-04-27
DOI: 10.1007/s10951-017-0520-6

• Task assignment with start time-dependent processing times for personnel
at check-in counters
• Authors: Emilio Zamorano; Annika Becker; Raik Stolletz
Abstract: Abstract This paper addresses a task assignment problem encountered by check-in counter personnel at airports. The problem consists of assigning multiskilled agents to a sequence of tasks in check-in counters. Because each task’s ending time is fixed to comply with the flight schedule, its processing time depends on the arrival of the assigned agents. We propose a mixed-integer program and a branch-and-price algorithm to solve this problem. We exploit the problem structure to efficiently formulate the pricing problems and improve computation time. Using real-world data from a German ground-handling agency, we conduct numerical studies to evaluate the performance of the proposed solutions.
PubDate: 2017-04-27
DOI: 10.1007/s10951-017-0523-3

• Approaches to modeling train scheduling problems as job-shop problems with
blocking constraints
• Authors: Julia Lange; Frank Werner
Abstract: Abstract The problem of scheduling a set of trains traveling through a given railway network consisting of single tracks, sidings and stations is considered. For every train a fixed route and travel times, an earliest departure time at the origin and a desired arrival time at the destination are given. A feasible schedule has to be determined which minimizes total tardiness of all trains at their destinations. This train scheduling problem is modeled as a job-shop scheduling problem with blocking constraints, where jobs represent trains and machines constitute tracks or track sections. Four MIP formulations without time-indexed variables are developed based on two different transformation approaches of parallel tracks and two different types of decision variables leading to job-shop scheduling problems with or without routing flexibility. A computational study is made on hard instances with up to 20 jobs and 11 machines to compare the MIP models in terms of total tardiness values, formulation size and computation time.
PubDate: 2017-04-27
DOI: 10.1007/s10951-017-0526-0

• Staff assignment with lexicographically ordered acceptance levels
• Authors: Tom Rihm; Philipp Baumann
Abstract: Abstract Staff assignment is a compelling exercise that affects most companies and organizations in the service industries. Here, we introduce a new real-world staff assignment problem that was reported to us by a Swiss provider of commercial employee scheduling software. The problem consists of assigning employees to work shifts subject to a large variety of critical and noncritical requests, including employees’ personal preferences. Each request has a target value, and deviations from the target value are associated with integer acceptance levels. These acceptance levels reflect the relative severity of possible deviations, e.g., for the request of an employee to have at least two weekends off, having one weekend off is preferable to having no weekend off and thus receives a higher acceptance level. The objective is to minimize the total number of deviations in lexicographical order of the acceptance levels. Staff assignment approaches from the literature are not applicable to this problem. We provide a binary linear programming formulation and propose a matheuristic for large-scale instances. The matheuristic employs effective strategies to determine the subproblems and focuses on finding good feasible solutions to the subproblems rather than proving their optimality. Our computational analysis based on real-world data shows that the matheuristic scales well and outperforms commercial employee scheduling software.
PubDate: 2017-04-26
DOI: 10.1007/s10951-017-0525-1

• Scheduling shared continuous resources on many-cores
• Authors: Ernst Althaus; André Brinkmann; Peter Kling; Friedhelm Meyer auf der Heide; Lars Nagel; Sören Riechers; Jiří Sgall; Tim Süß
Abstract: Abstract We consider the problem of scheduling a number of jobs on m identical processors sharing a continuously divisible resource. Each job j comes with a resource requirement . The job can be processed at full speed if granted its full resource requirement. If receiving only an x-portion of $$r_j$$ , it is processed at an x-fraction of the full speed. Our goal is to find a resource assignment that minimizes the makespan (i.e., the latest completion time). Variants of such problems, relating the resource assignment of jobs to their processing speeds, have been studied under the term discrete–continuous scheduling. Known results are either very pessimistic or heuristic in nature. In this article, we suggest and analyze a slightly simplified model. It focuses on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. It is shown that, even for unit size jobs, finding an optimal solution is NP-hard if the number of processors is part of the input. Positive results for unit size jobs include a polynomial-time algorithm for any constant number of processors. Since the running time is infeasible for practical purposes, we also provide more efficient algorithm variants: an optimal algorithm for two processors and a -approximation algorithm for m processors.
PubDate: 2017-04-19
DOI: 10.1007/s10951-017-0518-0

• Scheduling cleaning activities on trains by minimizing idle times
• Authors: Enrico Bartolini; Mauro Dell’Amico; Manuel Iori
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 mixed-integer program with a pseudo-polynomial 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: 2017-04-13
DOI: 10.1007/s10951-017-0517-1

• 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: 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: 2017-02-14
DOI: 10.1007/s10951-016-0507-8

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327

Home (Search)
Subjects A-Z
Publishers A-Z
Customise
APIs