FinCrime

A program that maintain its correctness in a multi-threaded environment is said to be a program. Thread-Safe Fundamentally, thread safety revolves around proper management of the shared state. In the absence of such proper management, the program could potentially spiral into an invalid state when executed in a multi-threaded environment. Defining Application’s State An application’s state is formed by the collective states of the individual objects that constitute it. An object’s state encompasses the data stored in its static or instance fields, which can influence its externally visible behavior. Furthermore, an object’s state may encompass fields from other dependent objects, creating a complex web of interconnected states within the application. Whether an object’s state need to be managed for concurrent access depends on its usage in your program. If an object is only ever accessed from a single thread, state management might not be needed! If multiple threads access the same mutable state of an object without proper synchronization, your application is technically broken. There are three ways to fix it — Don’t share the object across threads Make the object’s state immutable Implement proper synchronization for accessing the object’s shared state Using good Object Oriented Principles can help us in designing thread-safe classes. Thoughtful implementation of encapsulation, immutability, and precise specification of invariants can significantly reduce the effort required to create thread-safe classes, ultimately streamlining the development process. An important thing to note is that a program consisting of only thread-safe classes may not be thread-safe. Additionally, a program may be thread-safe even when some of its classes are not thread-safe. It all depends on how your objects interact with each other in your program! Defining Thread Safety A thread-safe class behaves correctly even when accessed from multiple threads, regardless of the scheduling or interleaving of the execution. The calling code needs no synchronization on its part when working with a thread-safe class. Thread-safe classes encapsulate the necessary synchronisation, relieving the client from the burden of providing their own. The need for synchronization arises when multiple threads access the same mutable state. However, stateless objects, by virtue of having no state to share, inherently possess thread safety. As a result, . stateless objects are always thread-safe Example of a thread-unsafe class Consider the following class that is used to find a certain number of primes, Java public class PrimeFinder {
    // Variable to count the number of invocations
    private int hitCount = 0;
    public int getHitCount() {
        return hitCount;
    }
    public List<Integer> findPrimes(int count) {
        hitCount++;
        // Find 'count' number of primes
        final List<Integer> primes = new ArrayList<>();
        for(int i = 2; i < Integer.MAX_VALUE; i++) {
            if(isPrime(i)) {
                primes.add(i);
                if(primes.size() == count) {
                    break;
                }
            }
        }
        return primes;
    }

    private boolean isPrime(int num) {
        for(int i = 2; i < num; i++) {
            if(num % i == 0) {
                return false;
            }
        }
        return true;
    }
} Note that the instance variable hitCount constitutes the state of any PrimeFinder object. Unfortunately, is not thread-safe, even though it would work fine in a single-threaded environment. This class is vulnerable to , as the operation to increase the , although seemingly atomic, is actually broken down into three distinct steps. Here is an example of an unlucky sequence of events causing to enter an invalid state. PrimeFinder lost updates hitCount hitCount Unlucky interleaving of execution causes hitCount to be 10 when it should be 11 Computation of incorrect results in case of some unlucky timings in a concurrent program is called a . The particular type of race condition that plagues our is called or . To eliminate this race condition, we must increment the hitCount in a single atomic operation. race condition PrimeFinder check-then-act read-modify-write There are several ways to fix the class. One such way is to use a thread-safe class inside . Here is the updated code, PrimeFinder PrimeFinder public class PrimeFinder {
    private final AtomicInteger hitCount = new AtomicInteger(0);
    public int getHitCount() {
        return hitCount.get();
    }
    public List<Integer> findPrimes(int count) {
        hitCount.getAndIncrement();
        // Find 'count' number of primes
        final List<Integer> primes = new ArrayList<>();
        for(int i = 2; i < Integer.MAX_VALUE; i++) {
            if(isPrime(i)) {
                primes.add(i);
                if(primes.size() == count) {
                    break;
                }
            }
        }
        return primes;
    }

    private boolean isPrime(int num) {
        for(int i = 2; i < num; i++) {
            if(num % i == 0) {
                return false;
            }
        }
        return true;
    }
} Using the atomic variable, we can ensure atomic operations on numbers and object references. Since the state of consists only of , which is thread-safe now, the class is thread-safe now! PrimeFinder hitCount PrimeFinder When a single element of state is added to a stateless class, the resulting class will be thread-safe if the state is entirely managed by a thread-safe object. Is it possible to add more state variables to PrimeFinder in a similar manner and still maintain its thread safety? Let us see… Consider the following (updated) class, PrimeFinder public class PrimeFinder {
    private final AtomicInteger numCache = new AtomicInteger(1);
    private final AtomicReference<List<Integer>> primeFactorCache = new AtomicReference<>(new ArrayList<>());
    
    // ...

    public List<Integer> findPrimeFactors(int num) {
        if(numCache.get() == num) {
            return new ArrayList<>(primeFactorCache.get());
        }
        // Find prime factors of 'num'
        final List<Integer> primeFactors = new ArrayList<>();
        for(int i = 2; i < num; i++) {
            if(isPrime(i) && num % i == 0) {
                primeFactors.add(i);
            }
        }
        numCache.set(num);
        primeFactorCache.set(new ArrayList<>(primeFactors));
        return primeFactors;
    }

    // ...

} The method is supposed to return prime factors of a number. It also stores a cache of the last number factorized and its factors. We have used atomic classes to store both the and the . findPrimeFactors numCache primeFactorCache Still, our class is not thread-safe! Can you spot the race condition here? Hint: There is a check-then-act race condition here! One invariant of our class is that the list will hold all prime factors of . Since two different variables participate in a single variant, these variables are not independent! In such cases, all the dependent variables must be updated in the same atomic operation! PrimeFinder primeFactorCache numCache To maintain state consistency, ensure that dependent state variables are updated in a single atomic operation. Intrinsic Locking in Java Every Java object can implicitly act as a lock for the purpose of synchronization. These built-in locks are what we call or . intrinsic locks monitor locks There is a built-in mechanism in Java to provide synchronization called a synchronized block. A synchronized block is a set of statements guarded by an intrinsic lock (object reference). Here is its syntax — synchronized (lock) {
  // Statements working with shared mutable state
} The lock is automatically acquired by an executing thread when it enters a synchronized block and is released when the block is exited. Since these intrinsic locks can be held by at most one executing thread at once, they allow exclusive access to the guarded code. A synchronized method is a synchronized block with the entire method as body and object as its lock. this Let us fix our class using intrinsic locks. PrimeFinder public class PrimeFinder {
    private final AtomicInteger numCache = new AtomicInteger(1);
    private final AtomicReference<List<Integer>> primeFactorCache = new AtomicReference<>(new ArrayList<>());
    
    // ...

    public List<Integer> findPrimeFactors(int num) {
        synchronized (this) {
            if (numCache.get() == num) {
                return new ArrayList<>(primeFactorCache.get());
            }
        }
        // Find prime factors of 'num'
        final List<Integer> primeFactors = new ArrayList<>();
        for(int i = 2; i < num; i++) {
            if(isPrime(i) && num % i == 0) {
                primeFactors.add(i);
            }
        }
        synchronized (this) {
            numCache.set(num);
            primeFactorCache.set(new ArrayList<>(primeFactors));
        }
        return primeFactors;
    }

    // ...

} With this, our class is thread-safe again! PrimeFinder With this, we reach the end of this blog. We discussed the fundamentals of thread safety in terms of program state and explored some basic synchronization techniques in Java. If you enjoy reading this blog, consider throwing in a like and subscribe to not miss future articles on Java concurrency! Also published . here

Safeguarding Concurrent Programs in Java: Thread Safety from an Object Oriented Perspective

THE MEMORABLE ASSASSINATION

In today’s episode of the Brains Byte Back podcast, we speak with , CEO of , an end-to-end platform that allows companies to achieve their expansion needs through finding, hiring, retaining, and paying talent. Pablo Miller Remoti To start the show Miller shares how Remoti is a total talent platform that connects companies with talent in Latin America, and advocates that the platform offers three main services: talent connection, talent employment, and people products. People products include retention plans, smooth onboarding and offboarding processes, and the upcoming launch of their recruitment app. He also shares the origin story of Remoti, explaining that the initial basis of the company was established in the UK seven years ago when Miller noticed the demand for salespeople in London’s fintech companies and started a small recruitment firm. He recognized the need for a different approach and aimed to build a business that understood and provided a unique service. While visiting Colombia, the country his mother is from, Miller witnessed the rise of second-generation Latin talent and the potential for innovation in the market and decided to set up operations in Colombia, serving clients from the US and UK. company culture The conversation then moves onto the topic of the future of and innovation. With this in mind, Remoti aims to connect Latin American professionals with global companies that can offer better opportunities and development. remote work Miller also shares how he believes remote work promotes and breaks down geographical barriers, providing opportunities for talented individuals who may not have access to the same resources locally. social mobility And finally, Miller shares insights on how to hire talent quickly and effectively for your business. He states that those looking to hire should consider international perspectives, local preferences, benefits, upskilling opportunities, and candidate output rather than focusing solely on universities. https://youtu.be/fM9YyO_so6I?embedable=true I’m the founder and CEO my main role and this business, it has been said, is to keep the lights on, turn off the fires and keep it all together. Remoti is a platform that allows companies to build technology hubs in Latin America. As I like to call it, we’re a total talent platform in the sense that we offer three services. Number one, we connect you to the talent. Number two, we employ the talent for you. And then number three, we call it people products. So we’re able to locally hire your talent and we have a number of retention products to ensure a smooth onboarding off-boarding and several retention plans. Alongside that will be launching our app in the next coming months, which allowed the whole recruitment process to be done for your template. Pablo Miller: Fantastic. thank you for joining us today, and thank you for taking a break from putting out those fires and making sure those lights are kept on. And I really want to kick off with how did Remoti first start? Samuel Brake Guia: So Remoti, which was formerly known as Fincrew, actually started in the UK seven years ago. So I was brought up in the UK. I was at Nottingham University, studying Politics and Sociology, and this was in 2008 when everyone hated the banks and the rise of Fintech started rising. So, I noticed that all these small, Fintechs in London, needed, graduate salespeople, and from Nottingham University, we set up a very small recruitment company. When I was doing that, I noticed that all the cool Fintech companies really didn’t like recruiters, they thought that we were transactional. They thought that we didn’t actually understand the company culture. Pablo Miller: So I wanted to build a business that was a bit different and the idea was actually set up the company in the US and then, my mother’s from Armenia, Quindío and I came on holiday to Colombia before I set up the business, and I saw something truly amazing happening in Latin America which was, first of all, the rise of, second-generation Latin talent, both locally and the ones that have gone abroad to study or work in other companies and have come back and secondly, and the markets here were just right for innovation and for disruption and so I had one investor at the time and I told him instead of, wiring the money to our Chase account in the US, can you wire it to our Bancolombia account here in Bogota and we set up the operation in Colombia, servicing US and UK clients. So we kind of trod along, working there, within their clients just operations here that everything was with outside markets and then the pandemic here and this is when everyone for okay, I don’t need to hire locally, Latin America is a market with a lot of potential. Let’s have a look at that time and that’s when Remoti was built in terms of being kind of the bridge between the West and LATAM. And that essentially has been now for the last three years. : Fantastic. I have to say, I do completely understand what you mean when you talk about the potential here in Latin America and I have to say as well that it’s great to speak with you being based in Bogota because I definitely do feel like there’s an energy within the startup ecosystem, especially in Medellin and Bogota that I really love and it’s so surprising to see. And most people might not think of that if they’ve not been down here of how much potential there is here. So it’s so great to hear of this success story coming out from essentially my own back garden, well where I live anyway, at least obviously not being from here myself, but I want to know on a separate note, Remoti, what’s the story behind that name? How did that come about? Samuel Brake Guia Yeah, great question. Just to kind of supplement what you’re saying, when people ask us, we’ve managed to scale a team, to 70 people. And we took very limited funding and our secret sauce has always been our people. There is great energy in this country. And people want to work for companies where they’re treated, where they’re respected and therefore this is why when foreign companies look at Latin America and Colombia and it’s a great place to start a business. Pablo Miller: So when we change the name from Fincrew which was meant to be like fintech recruitment to Remoti, we wanted to give a real remote work vibe and secondly, because we’re building a bunch of technology. If you are onboarding products of boarding products for our salary benchmark products, we want to obviously have the technology infrastructure, so really Remoti stands for remote technology infrastructure and we get good feedback from our clients because it says exactly what we do. Because ultimately you can’t just set up a remote team. Number one, it is very hard to hire local people if you’re based UK or China or whatever. And then to actually hire them properly to ensure that their payroll, legal taxes and all that are done accordingly and also to retain them. So that’s where the name remote technology infrastructure comes from that. If you want to just build a remote team, you just integrate pur platform into your business and off you go. That’s nice. Yeah, it does have that real startup vibe. I can see that in the name and I think it reflects what you do. We’ve obviously spoken a lot about the company here, but I would love to know some more insights. So can you share some insights on what companies have to do in order to secure top talent? Samuel Brake Guia: Yeah, so it’s also quite an interesting topic obviously, in the market that we’re in. Last year, our key markets, we work along with Fintech clients, we worked a lot with Web 3 clients, and obviously with the down market, we’ve had to find alternative markets, to find growth in these, tricky market conditions. So we look at one market that’s growing very fast for us is actually ERP Implementation Consultants. So these folks go into companies to implement in this SAP, Salesforce, Workday and traditionally you’d have to hire someone locally, and what these big institutions, found that actually make sense to have some folks based in Argentina, based in Cali, Bogota. And they design implementing, literally from here and it’s a remote role. Pablo Miller: So, for us, we’re very easy to work with in the sense that we find a client. They tell us what their needs are. We then tell them exactly where we believe in the region that can be a talent pool, we conduct salary benchmark reports, So we’re in contact with Finance to ensure that it’s in conjunction with them, We then assign a full team and that team, our slogan is “Quality at pace”, that team works full time for that assignment and then we’ll be able to deliver results very very quickly at the highest quality to our clients. : Fantastic. it sounds like you got it. Very nailed down. And I am so happy to see that there’s so much innovation in this space because I think remote work really does feel like it’s here to stay and as someone that feels the benefits of this. And I know so many other people have as well. It’s so exciting to see it flourish really. The benefits of this are just I think so profound that it’s great to see that you’re working on innovating in this space to make sure it prevails really. Samuel Brake Guia : Absolutely. And I think one of the key things, from my story. My mother was from Armenia, she traveled to the UK, my dad is English and we’re very fortunate that we went to, good schools, good universities, we learn how to communicate well. And that obviously gave us a lot of opportunities for me and my sister when it came to jobs. So really my vision with remote work is, I want to get that untouched talent of Latin America that has all that potential. We want to help them connect with companies that locally may not be able to pay them as well. May not be able to develop them as well, and may not be able to give them the opportunities. And so there’s a wonderful kind of social mobility angle to the rise of remote work. Pablo Miller : Yeah. Breaking down borders. That is a wonderful side effect of this, the remote work digital world that I can see here. And I also have to say I’ve seen on your blog that you have a post titled, how to recruit fast Six practical strategies to hire quickly. Now I would definitely recommend listeners, go and check that out. But while I have you here, I would love to cover a few insights that you can share based on this article, as well as your own knowledge and how our listeners can hire quickly and effectively. Samuel Brake Guia : Yeah, absolutely. I think one of the key things that, obviously supplements the title is that you’ve got to think internationally and at the same time, think realistic. So as you know being based in Medellin, someone from Medlelin is very different from someone in Bogota. So as a business you need to understand the differences of particular people and, particular geographical candidates who would like, in terms of benefits the way they want to work, some people want to work, hybrid, and someone people want to work remotely. Number two, you need to be able to give them access to upscale courses locally as well. if we’re looking, hiring someone in Europe, maybe they’re not that interested in, having English courses, for example, as opposed to candidates in Latin America, and number three, you need to obviously be open-minded and not be kind of judgmental about universities. Always look at the output that these candidates achieve. So if a candidate has done incredible work at a local startup, they should not be discounted if they haven’t been to Harvard or something. It’s very important to have these sort of mindsets when looking at hiring and connection. Pablo Miller I think that’s some solid advice there and I think it can be surprising just how much of a difference there can be when it comes to even small distances, like you mentioned, Medellin to Bogota. And I think you can find that across many countries and I do want to know, are there other companies operating in this space? And if so, how do you differentiate yourself from the competition? Samuel Brake Guia: : Great question. So HR tech, it’s certainly a crowded space and number two, I mean there’s a lot of companies now saying, I can help you find talent in Latin America, it’s cheap, etc. You have got to be very cautious about this in the sense that certain companies are trying to just sell Latin America for the cheap economic sense. But really Latin America is a great example of the modern workforce, the folks that are developers here, they not the ones that have been building databases in a bank for about 30 years, it’s that kind of millennial developer the self-taught, worked at startups. And so where we differentiate ourselves is that we have access to the modern workforce that can build modern digital products. And secondly, we’ve been focusing more on corporate clients, they hate finding new supplies for everything. So given that we’re a total talent platform. Pablo Miller They have three essential services from finding to hiring to retaining talent. It means the clients can with one provider, solve the whole problem. So when I look at competitive Ontop, fabulous business, great founders, but they just offer the payroll solutions, they don’t offer retention products. They don’t offer talent scout. And then obviously deal who are one of the pioneers and this amazing, payroll business. When the pandemic hit they got great technology, they really just focus on the payments and payroll side and so really if you don’t retain the candidates, it’s hard to offer them payroll. So this Remoti fits in well and we can offer all three services. Most importantly we have access to the modern workforce and we have tools in order to retain them and also to attract them to your business. That makes a lot of sense. I can see that and I do like the idea that this modern world is more of a meritocracy, it matters less where you are and just more about your skills and your ability. And I think that that’s really important because I really dislike the fact that so much is dictated by where you’re born. And I think that when job opportunities are open to everyone in the world, that just feels like it’s more of a meritocracy, the way it should be. And really my last question to you is what’s next on the horizon? Samuel Brake Guia: Yeah. absolutely. So, at the moment, as I mentioned we’ll be launching our app and our app is super interesting because, like most problems in life, most problems are caused by, bad communication. So, our industry has a very bad reputation for candidates not being given proper feedback or candidates not being fully prepared or candidates not being rejected probably. So we’ve got a communication tool that candidates can download and they seamlessly go through the whole recruitment process and all the communication between the candidate, client, and recruiter is in one place. Number two, in terms of the payroll, the digital wallet will be in the app so they can track their payments. Pablo Miller: They can also track when they will be paid. And number three will be building a marketplace where there’s going to be upsell. So we’re going to be offering our community of developer language courses and also development courses. And so really in one place, you’d be able to find a job. You’ll be able to grow financially. Number three, you’ll be able to upskill. So essentially we’re digitalizing this community and helping them, regardless of where you are in Latin America to find a great job, be paid accordingly and also to be upskilling. And that is really our passion for the modern workforce. Fantastic. if people are listening and they want to keep up with the work that you folks are doing. Pablo, what’s the best way for them to do that?Pablo Miller: So obviously the main channels, we have LinkedIn. We also have Instagram with Facebook and also on our website. We also have two offices, one in Bogota and Medellin, so people are welcome to come in for a coffee, would be delighted to host them. And, from candidates to clients, we have an open-door policy and are always very happy to virtually meet. Samuel Brake Guia: This article was originally published by on Samuel Brake Guia The Sociable.

Breaking Barriers: Remote Work's Impact on Social Mobility in Latin America

Instance Decomposition with Fixed Curriculum Increments

Hybrid Meta-Heuristic for Efficient Course Timetabling

Authors:
(1) Jo˜ao Almeida, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal;
(2) Jos´e Rui Figueira, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal;
(3) Alexandre P. Francisco, INESC-ID, Instituto Superior T´ecnico, Universidade de Lisboa Portugal;
(4) Daniel Santos, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal. 4 Algorithmic framework In this section, we explain the algorithmic framework of our meta-heuristic. In Subsection 4.1, we give a general overview. In Subsection 4.2, we introduce the instance decomposition and increment procedure. In Subsection 4.3, we present the heuristic for generating the initial timetables. In Subsection 4.4, we address the guided local search component. In Subsection 4.5, we address the adaptive large neighbourhood component. In Subsection 4.6, we address the variable neighbourhood search component. 4.1 Overview Our hybrid meta-heuristic uses mechanisms from adaptive large neighbourhood search (ALNS), guided local search (GLS), and variable neighbourhood search (VNS). Its generic representation is presented in Figure 1. Its inputs are the full set of curricula, L, and three stopping criteria, S1, S2, and S3. Additional parameters are also necessary for its functions and procedures, which are addressed in the following subsections. Its output is a feasible schedule, s∗ . Instead of solving the entire instance from the start, we decompose it by curricula and increment it iteratively until the set of curricula being solved, L′ , is equal to the entire set of curricula, L. The decomposition mechanism functions in the following way: a set of lectures belonging to a set of curricula is added to the problem. Then, we find a new feasible solution, s∗ , considering the current set of lectures, I′. When we have a feasible solution, we add the next set of curricula. Let us note that the assignments of each iteration can be changed if necessary in the following iterations. Our objective function, f(s ∗ ), represents the number of hard constraint violations in the current solution. Thus, the neighbourhoods are searched to find if there is a neighbour with fewer violations. The neighbourhood structures are explained in detail in Subsection 4.5. However, instead of using a regular objective function in this search, we introduce mechanisms for penalising certain features in the solution, which are useful for escaping local optima. Accordingly, after a certain number of iterations, the feature penalty vector, λ, is updated. The features and the update procedure are explained in detail in Subsection 4.4. However, sometimes this penalty is not enough to escape some local optima. To avoid those, we include a shaking phase, which occurs after a certain number of penalty recalculations without improvements. The number of local searches before updating the penalty vector is the stopping criterion S1. The number of penalty weight recalculations which is attempted before inducing a shaking phase is the stopping criterion S2. The duration of the shaking phase is the stopping criterion S3. The pseudo-code for this meta-heuristic is presented in Algorithm 1. 4.2 Instance decomposition and increment The procedure to increment the instance is straightforward. Curricula are added to the instance until a specific stopping criterion is met, or the entire set of curricula is included. We explore two different stopping criteria. One receives as input a fixed number of curricula to be added in each iteration, ρ. The other adds curricula until a certain number of hard constraint violations, f, is reached. Their respective pseudo-code algorithms are given in the Appendix. Algorithm 8 presents the fixed increments procedure and Algorithm 9 the violations-based increment procedure. Whenever a new curriculum, ℓ ′′, is added, its lectures, i ∈ aℓ ′′ , must be scheduled and added to the current solution, s∗ . The function which returns the schedule for each new curriculum is presented in the following subsection. Figure 2 provides a diagram of the procedure. We test two different sorting algorithms for deciding the order in which the curricula are added. The random sorting procedure chooses a random curriculum. The ordering procedure picks a degree, then, by ascending order of year, picks a class, and then adds the first and second trimesters, each corresponding to a different curriculum, ℓ, or timetable. This procedure is presented in Algorithm 2. 4.3 Initial solutions 4.4 Guided local search Considering each type of constraint violation as an objective, this methodology can be analysed as a multi-objective search technique. Effectively, what is happening is that out of the objective functions being regarded, the most challenging to improve are identified. Then, their weights, λi , are updated to help the search move towards non-dominated solutions that improve these objectives’ performance, even if the total sum of the effective violations increases. 4.5 Adaptive large neighbourhood search In ALNS, the local search is based on different neighbourhood structures. In each iteration, a neighbourhood structure, n, is selected based on a probability vector, p, and a local search is conducted. If a better solution is found, it replaces the bestknown solution. Let us note that we use an augmented objective function adapted from GLS procedures, f ′ (s). Then, based on the current solution characteristics and the previous successes of searches in each neighbourhood, the probability vector, p, is updated. The general algorithm framework is presented in Algorithm 5. To implement ALNS, it is necessary to define the set of neighbourhood structures, N, the procedure for updating the probability vector, p, and the stopping criterion. We established six main neighbourhood structures, which we named: worst slot, worst curriculum, worst professor, worst room type, different day, and precedence neighbourhoods. Moreover, each of them has two sub-types, named swap and non-swap. In each neighbourhood, a lecture is selected, and then, in the swap sub-type, its time slot is swapped with another lecture, and in the non-swap sub-type, it is randomly assigned to another time slot. The neighbourhoods follow a general framework that can be applied to each type of constraint violation. The first step is randomly selecting a lecture potentially causing violations. Then, either an adequate new time slot or an adequate swap lecture is randomly assigned. This adequacy is assessed based on the type of violation being caused. This general framework is presented in Figure 4. Specifically, each neighbourhood structure operates in the following manner: 4.6 Variable neighbourhood search In VNS, whenever local optima are identified, a shaking phase is used to move to different areas of the solution space. In our meta-heuristic, such a shaking phase is conducted if no improvement moves are found after a certain number of feature penalty updates are made. This shaking phase functions similarly to the ALNS algorithm, but every move is accepted instead of only those which introduce improvements. This phase is stopped after a number of iterations, S3. It is presented in Algorithm 7. This paper is available on arxiv under CC 4.0 license. Authors: (1) Jo˜ao Almeida, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (2) Jos´e Rui Figueira, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (3) Alexandre P. Francisco, INESC-ID, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (4) Daniel Santos, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal. Authors: (1) Jo˜ao Almeida, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (2) Jos´e Rui Figueira, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (3) Alexandre P. Francisco, INESC-ID, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (4) Daniel Santos, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal. 4 Algorithmic framework In this section, we explain the algorithmic framework of our meta-heuristic. In Subsection 4.1, we give a general overview. In Subsection 4.2, we introduce the instance decomposition and increment procedure. In Subsection 4.3, we present the heuristic for generating the initial timetables. In Subsection 4.4, we address the guided local search component. In Subsection 4.5, we address the adaptive large neighbourhood component. In Subsection 4.6, we address the variable neighbourhood search component. 4.1 Overview Our hybrid meta-heuristic uses mechanisms from adaptive large neighbourhood search (ALNS), guided local search (GLS), and variable neighbourhood search (VNS). Its generic representation is presented in Figure 1. Its inputs are the full set of curricula, L, and three stopping criteria, S1, S2, and S3. Additional parameters are also necessary for its functions and procedures, which are addressed in the following subsections. Its output is a feasible schedule, s∗ . Instead of solving the entire instance from the start, we decompose it by curricula and increment it iteratively until the set of curricula being solved, L′ , is equal to the entire set of curricula, L. The decomposition mechanism functions in the following way: a set of lectures belonging to a set of curricula is added to the problem. Then, we find a new feasible solution, s∗ , considering the current set of lectures, I′. When we have a feasible solution, we add the next set of curricula. Let us note that the assignments of each iteration can be changed if necessary in the following iterations. Our objective function, f(s ∗ ), represents the number of hard constraint violations in the current solution. Thus, the neighbourhoods are searched to find if there is a neighbour with fewer violations. The neighbourhood structures are explained in detail in Subsection 4.5. However, instead of using a regular objective function in this search, we introduce mechanisms for penalising certain features in the solution, which are useful for escaping local optima. Accordingly, after a certain number of iterations, the feature penalty vector, λ, is updated. The features and the update procedure are explained in detail in Subsection 4.4. However, sometimes this penalty is not enough to escape some local optima. To avoid those, we include a shaking phase, which occurs after a certain number of penalty recalculations without improvements. The number of local searches before updating the penalty vector is the stopping criterion S1. The number of penalty weight recalculations which is attempted before inducing a shaking phase is the stopping criterion S2. The duration of the shaking phase is the stopping criterion S3. The pseudo-code for this meta-heuristic is presented in Algorithm 1. 4.2 Instance decomposition and increment The procedure to increment the instance is straightforward. Curricula are added to the instance until a specific stopping criterion is met, or the entire set of curricula is included. We explore two different stopping criteria. One receives as input a fixed number of curricula to be added in each iteration, ρ. The other adds curricula until a certain number of hard constraint violations, f, is reached. Their respective pseudo-code algorithms are given in the Appendix. Algorithm 8 presents the fixed increments procedure and Algorithm 9 the violations-based increment procedure. Whenever a new curriculum, ℓ ′′, is added, its lectures, i ∈ aℓ ′′ , must be scheduled and added to the current solution, s∗ . The function which returns the schedule for each new curriculum is presented in the following subsection. Figure 2 provides a diagram of the procedure. We test two different sorting algorithms for deciding the order in which the curricula are added. The random sorting procedure chooses a random curriculum. The ordering procedure picks a degree, then, by ascending order of year, picks a class, and then adds the first and second trimesters, each corresponding to a different curriculum, ℓ, or timetable. This procedure is presented in Algorithm 2. 4.3 Initial solutions 4.4 Guided local search Considering each type of constraint violation as an objective, this methodology can be analysed as a multi-objective search technique. Effectively, what is happening is that out of the objective functions being regarded, the most challenging to improve are identified. Then, their weights, λi , are updated to help the search move towards non-dominated solutions that improve these objectives’ performance, even if the total sum of the effective violations increases. 4.5 Adaptive large neighbourhood search In ALNS, the local search is based on different neighbourhood structures. In each iteration, a neighbourhood structure, n, is selected based on a probability vector, p, and a local search is conducted. If a better solution is found, it replaces the bestknown solution. Let us note that we use an augmented objective function adapted from GLS procedures, f ′ (s). Then, based on the current solution characteristics and the previous successes of searches in each neighbourhood, the probability vector, p, is updated. The general algorithm framework is presented in Algorithm 5. To implement ALNS, it is necessary to define the set of neighbourhood structures, N, the procedure for updating the probability vector, p, and the stopping criterion. We established six main neighbourhood structures, which we named: worst slot, worst curriculum, worst professor, worst room type, different day, and precedence neighbourhoods. Moreover, each of them has two sub-types, named swap and non-swap. In each neighbourhood, a lecture is selected, and then, in the swap sub-type, its time slot is swapped with another lecture, and in the non-swap sub-type, it is randomly assigned to another time slot. The neighbourhoods follow a general framework that can be applied to each type of constraint violation. The first step is randomly selecting a lecture potentially causing violations. Then, either an adequate new time slot or an adequate swap lecture is randomly assigned. This adequacy is assessed based on the type of violation being caused. This general framework is presented in Figure 4. Specifically, each neighbourhood structure operates in the following manner: 4.6 Variable neighbourhood search In VNS, whenever local optima are identified, a shaking phase is used to move to different areas of the solution space. In our meta-heuristic, such a shaking phase is conducted if no improvement moves are found after a certain number of feature penalty updates are made. This shaking phase functions similarly to the ALNS algorithm, but every move is accepted instead of only those which introduce improvements. This phase is stopped after a number of iterations, S3. It is presented in Algorithm 7. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Breaking Down the Timetable Puzzle: IST's Algorithmic Framework

Authors:
(1) Jo˜ao Almeida, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal;
(2) Jos´e Rui Figueira, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal;
(3) Alexandre P. Francisco, INESC-ID, Instituto Superior T´ecnico, Universidade de Lisboa Portugal;
(4) Daniel Santos, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal. 3 The course timetabling problem for Instituto Superior T´ecnico In this section, we define the course timetabling problem for IST. In Subsection 3.1, we introduce the notation for the indices. In Subsection 3.2, we provide the required parameters. In Subsection 3.3, we characterise the decision and auxiliary variables. In Subsection 3.4, we explore the constraints that determine the feasibility of the timetables. In Subsection 3.5, we present the instances solved in our work. 3.1 Indices The indices are presented in this subsection. – i = 1, . . . , ni , are the indices related to the lectures; – j = 1, . . . , nj , are the indices related to the days; – k = 1, . . . , nk, are the indices related to the hour slots in each day; – t = 1, . . . , nt, are the indices related to the room types; – ℓ = 1, . . . , nℓ, are the indices related to the curricula; – p = 1, . . . , np, are the indices related to the professors; – µ = 1, . . . , nµ, are the indices related to the campi; 3.2 Parameters The parameters are presented in this subsection. They are divided into four groups. The first is related to associations between lectures, curricula, and professors. The second is related to lecture characteristics. The third is related to curricula and professor workloads. The fourth is related to rooms. 1. Related to associations between lectures, curricula and professors. – aℓ ∈ {1, . . . , ni}, is the set of lectures, i, which is part of a curricula, ℓ, for all ℓ = 1, . . . , nℓ. – bp ∈ {1, . . . , np}, is the set of lectures, i, taught by a professor, p, for all p = 1, . . . , np. 2. Related to lecture characteristics. – ci ∈ N, is the duration of a lecture, i, in hour slots, for all i = 1, . . . , ni . – di ∈ {1, . . . , ni}, is the set of lectures, i ̸= i, which cannot be taught on the same day as another lecture, i, for all i = 1, . . . , ni . – ei ∈ {1, . . . , ni}, is the set of lectures, i ̸= i, which must be taught before another lecture, i for all i = 1, . . . , ni . 3. Related to curricula and professor workloads. – mℓ ∈ N, is the maximum daily workload for a given curricula, ℓ, in number of hour slots, for all ℓ = 1, . . . , nℓ. – op ∈ N, is the maximum daily workload for a given professor, p, in number of hour slots, for all p = 1, . . . , np. – rℓ ∈ N, is the maximum consecutive workload for a given curricula, ℓ, in number of hour slots, for all ℓ = 1, . . . , nℓ. – sp ∈ N, is the maximum consecutive workload for a given professor, p, in number of hour slots, for all p = 1, . . . , np. 3.3 Variables The variables are presented in this subsection. 1. Decision variables. – xijk ∈ {0, 1}, is 1 if a lecture, i, is taught in a day, j, and hour slot, k; and 0 otherwise, for all i = 1, . . . , ni , j = 1, . . . , nj , k = 1, . . . , nk. 2. Auxiliary variables. – yjkℓ ∈ {0, 1}, is 1 if a curriculum, ℓ, has a lecture scheduled in a time slot, (j, k); and 0 otherwise, for all j = 1, . . . , nj , k = 1, . . . , nk, ℓ = 1, . . . , nℓ. – yjkp ∈ {0, 1}, is 1 if a professor, p, has a lecture scheduled in a time slot, (j, k); and 0 otherwise, for all j = 1, . . . , nj , k = 1, . . . , nk, p = 1, . . . , np. 3.4 Constraints The constraints that define the course timetabling problem at IST are presented in this subsection. They are divided into four groups. The first is related to curriculum, professor, and room availability. The second is related to curriculum and professor workloads. The third is related to campus changes. Finally, the fourth is related to lecture assignments. 1. Curriculum, professor and room availability. These constraints ensure that students, professors and rooms are available at the time of their assignments. (a) Professor and student juxtaposition. Students in a certain curriculum, ℓ, or professors, p, do not have more than one lecture assigned at any given time. (b) Room juxtaposition. There are enough rooms of a type, t, for the lectures, i, which must be taught in a room of that type, vit = 1. 2. Curriculum and professor workload. These constraints ensure that regulations regarding the maximum student and professor workloads are met. (a) Maximum daily workload. In a day, j, a curriculum, ℓ, or professor, p, does not have more hour slots, k, of lectures, i, assigned than the regulations allow, mℓ and op. (b) Maximum consecutive workloads. A curriculum, ℓ, or a professor, p, does not exceed their maximum allowed consecutive workload, rℓ or sp. 3. Lecture assignment. These constraints ensure that regulations regarding lecture assignments are met. (a) Single assignment. Each lecture, i, is assigned to a single time slot, (j, k). (b) Same day incompatibility. Two lectures, i and i, are not taught in the same day, j, if the regulations state that that is the case, i ∈ di . (c) Precedence. If there is a lecture, i, which must precede another lecture, i, i.e., i ∈ ei , then, i, must be taught in the same day as i, at an earlier hour, or a previous day. 4. Campus changes. These constraints ensure that regulations regarding student or professor campus changes within the same day are met. (a) Minimum required time. Students of a certain curriculum, ℓ, and professors, p, have enough time, uµµ, to change campus if they have two consecutive lectures, i and i, in different campi, gi ̸= gi. 3.5 Instances The real-world instance, denoted as IST Complete, includes 4102 lectures, 644 classes and 900 professors. The lectures take place in 2 campi. There are lectures in the first trimester, lectures in the second trimester, and lectures that must be scheduled for the whole semester. The semester lectures must be taught in the same time slot in both trimesters. Thus, both trimesters must be scheduled simultaneously. Accordingly, each class has two distinct timetables, each corresponding to a different curriculum. Similarly, professors and room types must have distinct timetables for each trimester. Lecture duration ranges from one to four hours, with each hour corresponding to two time slots. When there are consecutive lectures in different campi, students and professors must have at least one free time slot in between. Students and teachers can have eight hours of lectures in a single day; of those, only five hours can be taught consecutively. To expand the computational experiments, 30 random subdivisions with 200, 250, and 300 classes were obtained from instance IST Complete. IST has two campi where lectures are taught, with 168 and 39 rooms available for teaching. However, for the subdivisions, we considered 142 and 29 rooms for the campi. Each lecture must be assigned to a specific type of room based on its capacity. Instances from the 2007 International Timetabling Competition were also adapted and tested. These instances do not include multiple campi or trimesters. Moreover, maximum consecutive workload, precedence, and different day lectures were added, and unavailable slots from the original problem were not regarded. A summary of the instances is presented in Table 1. Since our instances include several characteristics that are not present in the competition instances, we decided to encode our instances with a different structure than the ones from ITC 2007. Specifically to facilitate the decomposition and increment procedures and to include other parameters such as lecture duration, campi, or trimester. This paper is available on arxiv under CC 4.0 license. Authors: (1) Jo˜ao Almeida, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (2) Jos´e Rui Figueira, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (3) Alexandre P. Francisco, INESC-ID, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (4) Daniel Santos, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal. Authors: (1) Jo˜ao Almeida, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (2) Jos´e Rui Figueira, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (3) Alexandre P. Francisco, INESC-ID, Instituto Superior T´ecnico, Universidade de Lisboa Portugal; (4) Daniel Santos, CEGIST, Instituto Superior T´ecnico, Universidade de Lisboa Portugal. 3 The course timetabling problem for Instituto Superior T´ecnico In this section, we define the course timetabling problem for IST. In Subsection 3.1, we introduce the notation for the indices. In Subsection 3.2, we provide the required parameters. In Subsection 3.3, we characterise the decision and auxiliary variables. In Subsection 3.4, we explore the constraints that determine the feasibility of the timetables. In Subsection 3.5, we present the instances solved in our work. 3.1 Indices The indices are presented in this subsection. – i = 1, . . . , ni , are the indices related to the lectures; – j = 1, . . . , nj , are the indices related to the days; – k = 1, . . . , nk, are the indices related to the hour slots in each day; – t = 1, . . . , nt, are the indices related to the room types; – ℓ = 1, . . . , nℓ, are the indices related to the curricula; – p = 1, . . . , np, are the indices related to the professors; – µ = 1, . . . , nµ, are the indices related to the campi; 3.2 Parameters The parameters are presented in this subsection. They are divided into four groups. The first is related to associations between lectures, curricula, and professors. The second is related to lecture characteristics. The third is related to curricula and professor workloads. The fourth is related to rooms. 1. Related to associations between lectures, curricula and professors. 1. Related to associations between lectures, curricula and professors. – aℓ ∈ {1, . . . , ni}, is the set of lectures, i, which is part of a curricula, ℓ, for all ℓ = 1, . . . , nℓ. – bp ∈ {1, . . . , np}, is the set of lectures, i, taught by a professor, p, for all p = 1, . . . , np. 2. Related to lecture characteristics. 2. Related to lecture characteristics. – ci ∈ N, is the duration of a lecture, i, in hour slots, for all i = 1, . . . , ni . – di ∈ {1, . . . , ni}, is the set of lectures, i ̸= i, which cannot be taught on the same day as another lecture, i, for all i = 1, . . . , ni . – ei ∈ {1, . . . , ni}, is the set of lectures, i ̸= i, which must be taught before another lecture, i for all i = 1, . . . , ni . 3. Related to curricula and professor workloads. 3. Related to curricula and professor workloads. – mℓ ∈ N, is the maximum daily workload for a given curricula, ℓ, in number of hour slots, for all ℓ = 1, . . . , nℓ. – op ∈ N, is the maximum daily workload for a given professor, p, in number of hour slots, for all p = 1, . . . , np. – rℓ ∈ N, is the maximum consecutive workload for a given curricula, ℓ, in number of hour slots, for all ℓ = 1, . . . , nℓ. – sp ∈ N, is the maximum consecutive workload for a given professor, p, in number of hour slots, for all p = 1, . . . , np. 3.3 Variables The variables are presented in this subsection. 1. Decision variables. Decision variables. – xijk ∈ {0, 1}, is 1 if a lecture, i, is taught in a day, j, and hour slot, k; and 0 otherwise, for all i = 1, . . . , ni , j = 1, . . . , nj , k = 1, . . . , nk. 2. Auxiliary variables. Auxiliary variables. – yjkℓ ∈ {0, 1}, is 1 if a curriculum, ℓ, has a lecture scheduled in a time slot, (j, k); and 0 otherwise, for all j = 1, . . . , nj , k = 1, . . . , nk, ℓ = 1, . . . , nℓ. – yjkp ∈ {0, 1}, is 1 if a professor, p, has a lecture scheduled in a time slot, (j, k); and 0 otherwise, for all j = 1, . . . , nj , k = 1, . . . , nk, p = 1, . . . , np. 3.4 Constraints The constraints that define the course timetabling problem at IST are presented in this subsection. They are divided into four groups. The first is related to curriculum, professor, and room availability. The second is related to curriculum and professor workloads. The third is related to campus changes. Finally, the fourth is related to lecture assignments. 1. Curriculum, professor and room availability. These constraints ensure that students, professors and rooms are available at the time of their assignments. (a) Professor and student juxtaposition. Students in a certain curriculum, ℓ, or professors, p, do not have more than one lecture assigned at any given time. (b) Room juxtaposition. There are enough rooms of a type, t, for the lectures, i, which must be taught in a room of that type, vit = 1. 2. Curriculum and professor workload. These constraints ensure that regulations regarding the maximum student and professor workloads are met. (a) Maximum daily workload. In a day, j, a curriculum, ℓ, or professor, p, does not have more hour slots, k, of lectures, i, assigned than the regulations allow, mℓ and op. (b) Maximum consecutive workloads. A curriculum, ℓ, or a professor, p, does not exceed their maximum allowed consecutive workload, rℓ or sp. 3. Lecture assignment. These constraints ensure that regulations regarding lecture assignments are met. (a) Single assignment. Each lecture, i, is assigned to a single time slot, (j, k). (b) Same day incompatibility. Two lectures, i and i, are not taught in the same day, j, if the regulations state that that is the case, i ∈ di . (c) Precedence. If there is a lecture, i, which must precede another lecture, i, i.e., i ∈ ei , then, i, must be taught in the same day as i, at an earlier hour, or a previous day. 4. Campus changes. These constraints ensure that regulations regarding student or professor campus changes within the same day are met. (a) Minimum required time. Students of a certain curriculum, ℓ, and professors, p, have enough time, uµµ, to change campus if they have two consecutive lectures, i and i, in different campi, gi ̸= gi. 3.5 Instances The real-world instance, denoted as IST Complete, includes 4102 lectures, 644 classes and 900 professors. The lectures take place in 2 campi. There are lectures in the first trimester, lectures in the second trimester, and lectures that must be scheduled for the whole semester. The semester lectures must be taught in the same time slot in both trimesters. Thus, both trimesters must be scheduled simultaneously. Accordingly, each class has two distinct timetables, each corresponding to a different curriculum. Similarly, professors and room types must have distinct timetables for each trimester. Lecture duration ranges from one to four hours, with each hour corresponding to two time slots. When there are consecutive lectures in different campi, students and professors must have at least one free time slot in between. Students and teachers can have eight hours of lectures in a single day; of those, only five hours can be taught consecutively. To expand the computational experiments, 30 random subdivisions with 200, 250, and 300 classes were obtained from instance IST Complete. IST has two campi where lectures are taught, with 168 and 39 rooms available for teaching. However, for the subdivisions, we considered 142 and 29 rooms for the campi. Each lecture must be assigned to a specific type of room based on its capacity. Instances from the 2007 International Timetabling Competition were also adapted and tested. These instances do not include multiple campi or trimesters. Moreover, maximum consecutive workload, precedence, and different day lectures were added, and unavailable slots from the original problem were not regarded. A summary of the instances is presented in Table 1. Since our instances include several characteristics that are not present in the competition instances, we decided to encode our instances with a different structure than the ones from ITC 2007. Specifically to facilitate the decomposition and increment procedures and to include other parameters such as lecture duration, campi, or trimester. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

FINCRIME

fincrime.net

-- employees

Since n.d.

COMPANY RANKING

FINCRIME

EVERGREEN INDEX #4212

Representing this company? Click here to claim and customize this page!

FinCrime WIKI

Apply to get your Tech Company News Page live on HackerNoon.com today!

FINCRIME

fincrime.net

-- employees

Since n.d.

COMPANY RANKING

FINCRIME

EVERGREEN INDEX #4212

RELATED COMPANIESRANK

STORIES ABOUT FINCRIME

Representing this company? Click here to claim and customize this page!

FinCrime WIKI

Apply to get your Tech Company News Page live on HackerNoon.com today!