for Journals by Title or ISSN
for Articles by Keywords
  Subjects -> COMPUTER SCIENCE (Total: 1747 journals)
    - ANIMATION AND SIMULATION (28 journals)
    - AUTOMATION (31 journals)
    - COMPUTER ARCHITECTURE (8 journals)
    - COMPUTER ENGINEERING (10 journals)
    - COMPUTER GAMES (11 journals)
    - COMPUTER GRAPHICS (30 journals)
    - COMPUTER PROGRAMMING (18 journals)
    - COMPUTER SCIENCE (1127 journals)
    - COMPUTER SECURITY (37 journals)
    - CYBERNETICS AND ROBOTICS (54 journals)
    - DATA BASE MANAGEMENT (13 journals)
    - DATA MINING (20 journals)
    - INFORMATION SYSTEMS (73 journals)
    - INTERNET (72 journals)
    - SOCIAL WEB (24 journals)
    - SOFTWARE (25 journals)
    - THEORY OF COMPUTING (6 journals)

COMPUTER SCIENCE (1127 journals)            First | 5 6 7 8 9 10 11 12     

Journal of Systems Architecture     Hybrid Journal   (Followers: 3)
Journal of Systems Integration     Open Access   (Followers: 1)
Journal of Systems Science and Complexity     Hybrid Journal   (Followers: 5)
Journal of Systems Science and Systems Engineering     Hybrid Journal   (Followers: 2)
Journal of Telecommunications Management     Full-text available via subscription   (Followers: 2)
Journal of the ACM     Full-text available via subscription   (Followers: 1)
Journal of the American Medical Informatics Association     Full-text available via subscription   (Followers: 13)
Journal of the Association for History and Computing     Open Access   (Followers: 4)
Journal of the Brazilian Computer Society     Open Access  
Journal of the Text Encoding Initiative     Open Access   (Followers: 1)
Journal of Theoretical and Computational Chemistry     Hybrid Journal   (Followers: 7)
Journal of Transplantation     Open Access   (Followers: 3)
Journal of Transportation Systems Engineering and Information Technology     Full-text available via subscription   (Followers: 12)
Journal of Turbulence     Hybrid Journal  
Journal of Urban Regeneration and Renewal     Full-text available via subscription   (Followers: 10)
Journal of Visual Communication and Image Representation     Hybrid Journal   (Followers: 5)
Journal of VLSI Design Tools & Technology     Full-text available via subscription  
Journal of Water and Land Development     Open Access   (Followers: 1)
Journal of Zhejiang University SCIENCE C     Hybrid Journal  
Journal on Chain and Network Science     Full-text available via subscription   (Followers: 2)
Journal on Data Semantics     Hybrid Journal   (Followers: 3)
Journal on Multimodal User Interfaces     Hybrid Journal   (Followers: 3)
Jurnal Ilmu Komputer dan Informasi     Open Access  
Jurnal Informatika     Open Access   (Followers: 2)
Jurnal Informatika     Open Access   (Followers: 3)
Jurnal INKOM : Jurnal Informatika, Sistem Kendali dan Komputer     Open Access   (Followers: 1)
Jurnal Sistem Komputer     Open Access  
Jurnal Teknologi     Open Access   (Followers: 1)
KI - K√ľnstliche Intelligenz     Hybrid Journal  
Knowledge and Information Systems     Hybrid Journal   (Followers: 10)
Knowledge Management Research & Practice     Hybrid Journal   (Followers: 15)
Kybernetes     Hybrid Journal   (Followers: 1)
Landscape and Ecological Engineering     Hybrid Journal   (Followers: 3)
Language & Communication     Hybrid Journal   (Followers: 13)
Language Resources and Evaluation     Hybrid Journal   (Followers: 6)
Learning Technologies, IEEE Transactions on     Hybrid Journal   (Followers: 9)
Lecture Notes in Computer Science     Hybrid Journal   (Followers: 1)
Legal Theory     Hybrid Journal   (Followers: 7)
Leonardo     Hybrid Journal   (Followers: 9)
Library Hi Tech News     Hybrid Journal   (Followers: 622)
Library Technology Reports     Full-text available via subscription   (Followers: 137)
Linear Algebra and its Applications     Full-text available via subscription   (Followers: 2)
Literary and Linguistic Computing     Hybrid Journal   (Followers: 6)
LMS Journal of Computation and Mathematics     Free  
Logic and Analysis     Hybrid Journal  
Logica Universalis     Hybrid Journal  
Macromolecular Reaction Engineering     Hybrid Journal  
Magnetics Letters, IEEE     Hybrid Journal   (Followers: 1)
Management International Review     Hybrid Journal   (Followers: 5)
Management of Environmental Quality: An International Journal     Hybrid Journal   (Followers: 4)
Manufacturing Engineer     Hybrid Journal   (Followers: 4)
Marine Genomics     Hybrid Journal   (Followers: 1)
Mass Communication & Society     Hybrid Journal   (Followers: 6)
Material Religion : The Journal of Objects, Art and Belief     Full-text available via subscription   (Followers: 8)
Materials Science in Semiconductor Processing     Hybrid Journal   (Followers: 2)
Mathematical and Computer Modelling of Dynamical Systems: Methods, Tools and Applications in Engineering and Related Sciences     Hybrid Journal   (Followers: 1)
Mathematical Computation     Open Access  
Mathematical Problems in Engineering     Open Access   (Followers: 3)
Mathematical Structures in Computer Science     Hybrid Journal   (Followers: 3)
Mathematics in Computer Science     Hybrid Journal   (Followers: 1)
MATICS     Open Access  
Measurement Science Review     Open Access   (Followers: 1)
Mediators of Inflammation     Open Access   (Followers: 2)
Medical and Biological Engineering and Computing     Hybrid Journal   (Followers: 2)
Memetic Computing     Hybrid Journal  
Mendeleev Communications     Full-text available via subscription  
Metals and Materials International     Hybrid Journal   (Followers: 1)
Metascience     Hybrid Journal   (Followers: 1)
Method & Theory in the Study of Religion     Hybrid Journal   (Followers: 7)
Methodology And Computing In Applied Probability     Hybrid Journal   (Followers: 3)
Methods in Next Generation Sequencing     Full-text available via subscription  
Microbial Informatics and Experimentation     Open Access   (Followers: 2)
Microprocessors and Microsystems     Hybrid Journal   (Followers: 4)
Microsystem Technologies     Hybrid Journal   (Followers: 1)
Mineral Processing and Extractive Metallurgy Review: An International Journal     Hybrid Journal  
Mobile Computing     Open Access  
Mobile Networks and Applications     Hybrid Journal   (Followers: 6)
Modeling, Identification and Control     Open Access  
Modelling and Simulation in Engineering     Open Access   (Followers: 4)
Modelling and Simulation in Materials Science and Engineering     Hybrid Journal   (Followers: 7)
Molecular Simulation     Hybrid Journal   (Followers: 2)
Multiagent and Grid Systems     Hybrid Journal  
Multidimensional Systems and Signal Processing     Hybrid Journal  
Multimedia Systems     Hybrid Journal  
Multimedia Tools and Applications     Hybrid Journal   (Followers: 2)
Multiscale Modeling and Simulation     Full-text available via subscription   (Followers: 2)
Nano Research     Hybrid Journal   (Followers: 4)
Nanotechnologies in Russia     Hybrid Journal   (Followers: 1)
Nanotechnology Magazine, IEEE     Full-text available via subscription   (Followers: 12)
National Science Review     Hybrid Journal  
Natural Computing     Hybrid Journal   (Followers: 1)
Natural Language & Linguistic Theory     Hybrid Journal   (Followers: 7)
Natural Language Engineering     Hybrid Journal   (Followers: 2)
Network and Communication Technologies     Open Access   (Followers: 3)
Network: Computation in Neural Systems     Hybrid Journal   (Followers: 4)
Networks and Spatial Economics     Hybrid Journal  
Networks: an International Journal     Hybrid Journal   (Followers: 3)
Neural Computation     Hybrid Journal   (Followers: 5)
Neural Computing and Applications     Hybrid Journal   (Followers: 1)
Neural Networks     Hybrid Journal   (Followers: 6)

  First | 5 6 7 8 9 10 11 12     

Journal Cover Journal of Scheduling
   Journal TOC RSS feeds Export to Zotero [5 followers]  Follow    
   Hybrid Journal Hybrid journal (It can contain Open Access articles)
     ISSN (Print) 1099-1425 - ISSN (Online) 1094-6136
     Published by Springer-Verlag Homepage  [2210 journals]   [SJR: 1.857]   [H-I: 34]
  • Novel dual discounting functions for the Internet shopping optimization
           problem: new algorithms
    • Abstract: Abstract One of the very important topics in discrete optimization, motivated by practical applications, is Internet shopping, which is becoming increasingly popular each year. More classical versions of the Internet shopping optimization problem (ISOP) are closely related to the facility location problem and some scheduling problems and have been intensively studied in the literature. In this paper, extensions of the problem are defined and studied. The issue is to buy all the necessary products for a minimum total possible price. This includes all prices of products as well as shipping costs. Studies in this paper include the ISOP with price sensitive discounts and a newly defined optimization problem: the ISOP including two different discounting functions, namely a shipping cost function as well as a price discounting function. First, these are formulated as mathematical programming problems. Then, some algorithms are constructed and extensively tested in a computational experiment.
      PubDate: 2014-08-17
  • Real-life examination timetabling
    • Abstract: Abstract An examination timetabling problem at a large American university is presented. Although there are some important differences, the solution approach is based on the ITC 2007 winning solver which is integrated in the open source university timetabling system UniTime. In this work, nine real world benchmark data sets are made publicly available and the results on four of them are presented in this paper. A new approach to further decreasing the number of student conflicts by allowing some exams to be split into multiple examination periods is also studied.
      PubDate: 2014-08-09
  • Rescheduling for machine disruption to minimize makespan and maximum
    • Abstract: Abstract We consider a scheduling problem where a set of jobs has already been scheduled to minimize some cost objective on a single machine when the machine becomes unavailable for a period of time. The decision-maker needs to reschedule the jobs without excessively disrupting the original schedule. The disruption is measured as the maximum time deviation, for any given job, between the original and new schedules. We examine a general model where the maximum time disruption appears both as a constraint and as part of the cost objective. For a scheduling cost modeled as the makespan or maximum lateness, we provide a pseudopolynomial time optimal algorithm, a constant factor approximation algorithm, and a fully polynomial time approximation scheme. The approximation algorithm has an asymptotically achievable worst-case performance ratio of 2 and has average performance close to optimal. Managerial insights are given on how scheduling costs are affected by machine disruption and the approximation algorithm.
      PubDate: 2014-08-01
  • Frequency capping in online advertising
    • Abstract: Abstract We study the following online problem. There are n advertisers. Each advertiser \(a_i\) has a total demand \(d_i\) and a value \(v_i\) for each supply unit. Supply units arrive one by one in an online fashion, and must be allocated to an agent immediately. Each unit is associated with a user, and each advertiser \(a_i\) is willing to accept no more than \(f_i\) units associated with any single user (the value \(f_i\) is called the frequency cap of advertiser \(a_i\) ). The goal is to design an online allocation algorithm maximizing the total value. We first show a deterministic \(3/4\) -competitiveness upper bound, which holds even when all frequency caps are \(1\) , and all advertisers share identical values and demands. A competitive ratio approaching \(1-1/e\) can be achieved via a reduction to a different model considered by Goel and Mehta (WINE ‘07: Workshop on Internet and Network, Economics: 335–340, 2007). Our main contribution is analyzing two \(3/4\) -competitive greedy algorithms for the cases of equal values, and arbitrary valuations with equal integral demand to frequency cap ratios. Finally, we give a primal-dual algorithm which may serve as a good starting point for improving upon the ratio of \(1-1/e\) .
      PubDate: 2014-08-01
  • Flow shop batching and scheduling with sequence-dependent setup times
    • Abstract: Abstract This paper addresses the flow shop batching and scheduling problem where sequence-dependent family setup times are present and the objective is to minimize makespan. We consider violating the group technology assumption by dividing product families into batches. In order to reduce setup times, inconsistent batches are formed on different machines, which lead to non-permutation schedules. To the best of our knowledge, this is the first time that the splitting of job families into inconsistent batches has been considered in a flow shop system. A tabu search algorithm is developed which contains several neighbourhood functions, double tabu lists and a multilevel diversification structure. Compared to the state-of-the-art meta-heuristics for this problem, the proposed tabu search algorithm achieves further improvement when the group scheduling assumption is dropped. Also, various experiments conducted on the benchmark problem instances confirm the benefits of batching. Therefore, it will be prudent for the practitioners to consider adopting inconsistent batches and non-permutation schedules to improve their operational efficiency within a reasonable amount of computational effort.
      PubDate: 2014-08-01
  • Single-processor scheduling with time restrictions
    • Abstract: Abstract We consider the following list scheduling problem. We are given a set \(S\) of jobs which are to be scheduled sequentially on a single processor. Each job has an associated processing time which is required for its processing. Given a particular permutation of the jobs in \(S\) , the jobs are processed in that order with each job started as soon as possible, subject only to the following constraint: For a fixed integer \(B \ge 2\) , no unit time interval \([x, x+1)\) is allowed to intersect more than \(B\) jobs for any real \(x\) . It is not surprising that this problem is NP-hard when the value \(B\) is variable (which is typical of many scheduling problems). There are several real world situations for which this restriction is natural. For example, suppose in addition to our jobs being executed sequentially on a single main processor, each job also requires the use of one of \(B\) identical subprocessors during its execution. Each time a job is completed, the subprocessor it was using requires one unit of time in order to reset itself. In this way, it is never possible for more than \(B\) jobs to be worked on during any unit interval. In this paper we carry out a classical worst-case analysis for this situation. In particular, we show that any permutation of the jobs can be processed within a factor of \(2-1/(B-1)\) of the optimum (plus an additional small constant) when \(B \ge 3\) and this factor is best possible. For the case \(B=2\) , the situation is rather different, and in this case the corresponding factor we establish is \(4/3\) (plus an additional small constant), which is also best possible. It is fairly rare that best possible bounds can be obtained for the competitive ratios of list scheduling problems of this general type.
      PubDate: 2014-08-01
  • Optimization of inland shipping
    • Abstract: Abstract In this paper, we explore problems and algorithms related to the optimisation of locks, as used in inland shipping. We define several optimisation problems associated with inland shipping. We prove that the problem of scheduling a lock is NP-hard if one allows multiple ships to go through in the same lock operation. The single-ship lock optimization problem can, however, be solved in polynomial time and a novel deterministic scheduling algorithm for solving this problem is presented in this paper.
      PubDate: 2014-08-01
  • On the configuration-LP for scheduling on unrelated machines
    • Abstract: Abstract Closing the approximability gap between \(3/2\) and 2 for the minimum makespan problem on unrelated machines is one of the most important open questions in scheduling. Almost all known approximation algorithms for the problem are based on linear programs (LPs). In this paper, we identify a surprisingly simple class of instances which constitute the core difficulty for LPs: the so far hardly studied unrelated graph balancing case in which each job can be assigned to at most two machines. We prove that already for this basic setting the strongest LP-relaxation studied so far—the configuration-LP—has an integrality gap of 2, matching the best known approximation factor for the general case. This points toward an interesting direction of future research. For the objective of maximizing the minimum machine load in the unrelated graph balancing setting, we present an elegant purely combinatorial 2-approximation algorithm with only quadratic running time. Our algorithm uses a novel preprocessing routine that estimates the optimal value as good as the configuration-LP. This improves on the computationally costly LP-based algorithm by Chakrabarty et al. (Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS 2009), pp 107–116, 2009) that achieves the same approximation guarantee.
      PubDate: 2014-08-01
  • Line search method for solving a non-preemptive strictly periodic
           scheduling problem
    • Abstract: Abstract We study a non-preemptive strictly periodic scheduling problem. This problem arises for example in the avionic field where a set of \(N\) periodic tasks (measure of a sensor, data presentation, etc.) has to be scheduled on \(P\) processors distributed on the plane. In this article, we consider an existing heuristic which is based on the notion of equilibrium. Following a game theory analogy, each task tries successively to optimize its own schedule and, therefore, to produce the best response, given the other schedules. This iterative process continues until an equilibrium is reached. We present a new method to compute the best response which significantly improves the previously proposed heuristic, and compares favorably with MILP solutions.
      PubDate: 2014-07-31
  • Shift rostering using decomposition: assign weekend shifts first
    • Abstract: Abstract This paper introduces a shift rostering problem that surprisingly has not been studied in the literature: the weekend shift rostering problem. It is motivated by our experience that employees’ shift preferences predominantly focus on the weekends, since many social activities happen during weekends. The weekend rostering problem (WRP) addresses the rostering of weekend shifts, for which we design a problem-specific heuristic. We consider the WRP as the first phase of the shift rostering problem. To complete the shift roster, the second phase assigns the weekday shifts. This decomposition reflects how shift rosters are often created manually in practice, which makes the decomposition method proposed in this paper a more intuitive approach for business users compared to approaches without this decomposition. We believe that such approaches enable business users to effectively analyze and steer the outcomes of algorithms for shift rostering especially on criteria that are relevant to them such as those concerning weekends. We analyze and discuss effects of this two-phase approach both on the weekend shift roster and on the roster as a whole. We demonstrate that our first-phase weekend rostering heuristic is effective both on generated instances and real-life instances. For situations where the weekend shift roster is one of the key determinants of the quality of the complete roster, our two-phase approach is shown to be effective.
      PubDate: 2014-07-26
  • On-line preemptive machine scheduling with        class="a-plus-plus inline-equation id-i-eq1">        class="a-plus-plus equation-source format-t-e-x">\(\ell
    norm on two uniform machines
    • Abstract: Abstract One of the basic and fundamental scheduling problems is to minimize the machine completion time vector in the \(\ell _p\) norm, a direct extension of the well-studied objective makespan ( \(l_{\infty }\) norm), on parallel machines. We concentrate on the on-line and preemptive version of this problem where jobs arrive one by one over a list to be allocated to two uniform machines with job preemption permitted. We present a best possible deterministic on-line scheduling algorithm for this problem along with a matching lower bound, generalizing existing results for the identical machines scheduling problem in the literature. One notable feature of this work is the highly involved technicality compared to similar analysis in the existing literature, mainly due to the intrinsic unavailability of a closed-form formula for the competitive ratio.
      PubDate: 2014-07-05
  • Multipurpose machine scheduling with rejection and identical job
           processing times
    • Abstract: Abstract We study a set of scheduling problems on a uniform machine setting. We focus on the case of equal processing time jobs with the additional feature of job rejection. Jobs can either be processed on a predefined set of machines or rejected. Rejected jobs incur a rejection penalty and have no effect on the scheduling criterion under consideration. A solution to our problems consists of partitioning the jobs into two subsets, \(A\) and \(\overline{A}\) , which are the set of accepted and the set of rejected jobs, respectively. In addition, jobs in set \(A\) have to be scheduled on the \(m\) machines. We evaluate the quality of a solution by two criteria. The first, \(F_{1}\) , can be any regular scheduling criterion, while the latter, \(F_{2}\) , is the total rejection cost. We consider two possible types of regular scheduling criteria; the former is a maximization criterion, while the latter is a summation criterion. For each criterion type we consider four different problem variations. We prove that all four variations are solvable in polynomial time for \(any\) maximization type of a regular scheduling criterion. When the scheduling criterion is of summation type, we show that only one of the four problem variations is solvable in polynomial time. We provide a pseudo-polynomial time algorithms to solve interesting variants of the \(\mathcal {NP}\) -hard problems, as well as a polynomial time algorithm that solves various other special cases.
      PubDate: 2014-07-05
  • Time-hierarchical scheduling
    • Abstract: Abstract In this paper, the general time hierarchical planning and scheduling approach is introduced, which integrates both detailed scheduling and due date assignment for an online problem. In this approach, time is divided into intervals of increasing size, and the different sizes form a hierarchy. We show that for a simplified model, a multiple level bin packing approach is an approximation algorithm, and we further prove that under weak assumptions, the approximation quality is bounded independently of the depth of the hierarchy.
      PubDate: 2014-06-19
  • Solving multi-activity multi-day shift scheduling problems with a hybrid
    • Abstract: Abstract This paper addresses a multi-activity multi-day shift scheduling problem in a continuous and flexible environment including a heterogeneous workforce. Given days-off schedules associated with each employee, our objective is to construct and assign admissible multi-activity shifts to employees on their work days in a way that minimizes under-staffing and over-staffing with a restricted budget on workforce cost. A hybrid heuristic which combines tabu search with a branch-and-bound procedure is proposed to solve the problem. The computational experiments prove that our method provides good schedules in relatively short computing times.
      PubDate: 2014-06-06
  • An adaptive artificial bee colony and late-acceptance hill-climbing
           algorithm for examination timetabling
    • Abstract: Abstract The artificial bee colony (ABC) is a population-based metaheuristic that mimics the foraging behaviour of honeybees in order to produce high-quality solutions for optimisation problems. The ABC algorithm combines both exploration and exploitation processes. In the exploration process, the worker bees are responsible for selecting a random solution and applying it to a random neighbourhood structure, while the onlooker bees are responsible for choosing a food source based on a selection strategy. In this paper, a disruptive selection strategy is applied within the ABC algorithm in order to improve the diversity of the population and prevent premature convergence in the evolutionary process. A self-adaptive strategy for selecting neighbourhood structures is added to further enhance the local intensification capability (adaptively choosing the neighbourhood structure helps the algorithm to escape local optima). Finally, a modified ABC algorithm is hybridised with a local search algorithm, i.e. the late-acceptance hill-climbing algorithm, to quickly descend to a good-quality solution. The experiments show that the ABC algorithm with the disruptive selection strategy outperforms the original ABC algorithm. The hybridised ABC algorithm also outperforms the lone ABC algorithm when tested on examination timetabling problems.
      PubDate: 2014-06-01
  • Single-machine scheduling with periodic maintenance to minimize makespan
    • Abstract: Abstract In this paper, a single-machine scheduling problem with periodic maintenance and non-preemptive jobs is considered. The objective is to minimize the makespan. It shows that the classical list scheduling (LS) algorithm, the longest processing time first (LPT) algorithm, and the modified longest processing time first (MLPT) algorithm all have the same worst-case ratio and the same computational complexity for the considered problem. To compare the performances of three considered algorithms in detail, the worst-case ratios of algorithms are formed as single-variable functions of the total number of maintenance activities needed in the optimal schedule. Analysis results show that the bound associated with the LS algorithm is always dominated by the bound associated with the LPT algorithm, and the latter is always dominated by the bound associated with the MLPT algorithm.
      PubDate: 2014-06-01
  • Online scheduling with immediate and reliable lead-time quotation
    • Abstract: Abstract This paper studies an online scheduling problem with immediate and reliable lead-time quotation. A manufacturer either accepts an order by quoting a reliable lead-time on its arrival or rejects it immediately. The objective is to maximize the total revenue of completed orders. Keskinocak et al. (Management Science 47(2):264–279, 2001) studied a linear revenue function in a discrete model with integer release time of order, and proposed a competitive strategy Q-FRAC. This paper investigates a relaxed revenue function in both discrete and continuous models where orders are released at integer and real time points, respectively. For the discrete model, we present a revised Q-FRAC strategy that is optimal in competitiveness for concave and linear revenue functions with unit length and uniform weight of order, improving the previous results in Keskinocak et al. (Management Science 47(2):264–279, 2001). For the scenario with uniform length $p$ and nonuniform weight of order, we prove an optimal strategy for the case with $p=1$ and the nonexistence of competitive strategies for the case with $p>1$ . For the continuous model, we present an optimal strategy in competitiveness for the case with uniform weight of order and linear revenue functions, and prove the nonexistence of competitive strategies for the other case with nonuniform weight of order.
      PubDate: 2014-06-01
  • A preemptive bound for the Resource Constrained Project Scheduling Problem
    • Abstract: Abstract The Resource Constrained Project Scheduling Problem is one of the most intensively investigated scheduling problems. It requires scheduling a set of interrelated activities, while considering precedence relationships, and limited renewable resources allocation. The objective is to minimize the project duration. We propose a new destructive lower bound for this challenging ${\mathcal {NP}}$ -hard problem. Starting from a previously suggested LP model, we propose several original valid inequalities that aim at tightening the model representation. These new inequalities are based on precedence constraints, incompatible activity subsets, and nonpreemption constraints. We present the results of an extensive computational study that was carried out on 2,040 benchmark instances of PSPLIB, with up to 120 activities, and that provide strong evidence that the new proposed lower bound exhibits an excellent performance. In particular, we report the improvement of the best known lower bounds of 5 instances.
      PubDate: 2014-06-01
  • Iterated Local Search for single-machine scheduling with
           sequence-dependent setup times to minimize total weighted tardiness
    • Abstract: Abstract We present an Iterated Local Search (ILS) algorithm for solving the single-machine scheduling problem with sequence-dependent setup times to minimize the total weighted tardiness. The proposed ILS algorithm exhibits several distinguishing features, including a new neighborhood structure called Block Move and a fast incremental evaluation technique, for evaluating neighborhood solutions. Applying the proposed algorithm to solve 120 public benchmark instances widely used in the literature, we achieve highly competitive results compared with a recently proposed exact algorithm and five sets of best solutions of state-of-the-art metaheuristic algorithms in the literature. Specifically, ILS obtains the optimal solutions for 113 instances within a reasonable time, and it outperforms the previous best-known results obtained by metaheuristic algorithms for 34 instances and matches the best results for 82 instances. In addition, ILS is able to obtain the optimal solutions for the remaining seven instances under a relaxed time limit, and its computational efficiency is comparable with the state-of-the-art exact algorithm by Tanaka and Araki (Comput Oper Res 40:344–352, 2013). Finally, on analyzing some important features that affect the performance of ILS, we ascertain the significance of the proposed Block Move neighborhood and the fast incremental evaluation technique.
      PubDate: 2014-06-01
  • Linear programming-based algorithms for the minimum makespan high
           multiplicity jobshop problem
    • Abstract: Abstract We study a generalized version of the minimum makespan jobshop problem in which multiple instances of each job are to be processed. The system starts with specified inventory levels in all buffers and finishes with some desired inventory levels of the buffers at the end of the planning horizon. A schedule that minimizes the completion time of all the operations is sought. We develop a polynomial time asymptotic approximation procedure for the problem. That is, the ratio between the value of the delivered solution and the optimal one converge into one, as the multiplicity of the problem increases. Our algorithm uses the solution of the linear relaxation of a time-indexed Mixed-Integer formulation of the problem. In addition, a heuristic method inspired by this approximation algorithm is presented and is numerically shown to out-perform known methods for a large set of standard test problems of moderate job multiplicity.
      PubDate: 2014-04-08
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327
About JournalTOCs
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-2014